[转]常用排序算法分析与实现（一）（Java版）

在已经排好序的序列中查找待插入的元素的插入位置，并将待插入元素插入到有序列表中的过程。
 
将数组分成两部分，初始化时，前部分数组为只有第一个元素，用来存储已排序元素，我们这里叫 arr1 ；后部分数组的元素为除第一个元素的所有元素，为待排序或待插入元素，我们这里叫 arr2 。
排序时使用二层循环：第一层对 arr2 进行循环，每次取后部分数组（待排序数组）里的第一个元素（我们称为待排序元素或称待插入元素） e1 ，然后在第二层循环中对 arr1 （已排好序的数组）从第一个元素往后进行循环，查到第一个大于待插入元素（如果是升序排列）或第一个小于待插入元素（如果是降序排列） e2 ，然后对 arr1 从 e2 元素开始往后的所有元素向后移，最后把 e1 插入到原来 e2 所在的位置。这样反复地对 arr2 进行循环，直到 arr2 中所有的待插入的元素都插入到 arr1 中。 
Java代码 
package sort;  
  
import java.util.Comparator;  
  
/** 
 *  直接插入排序算法 
 * @author jzj 
 * @date 2009-12-5 
 *  
 * @param <E> 
 */  
public class InsertSort<E extends Comparable<E>> extends Sort<E> {  
  
    /** 
     * 排序算法的实现，对数组中指定的元素进行排序 
     * @param array 待排序的数组 
     * @param from 从哪里开始排序 
     * @param end 排到哪里 
     * @param c 比较器 
     */  
    public void sort(E[] array, int from, int end, Comparator<E> c) {  
  
        /* 
         * 第一层循环：对待