排序算法-插入排序

插入排序




基本思路：

基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。

问题描述：
     举个例子来说，就用前面的数组，我们要对一个有5个元素的数组进行升序排列，假设
第一个元素的值被假定为已排好序了，那么我们就将第2 个元素与数组中的部分进行比较，
如果第2 个元素的值较小，则将它插入到第1 个元素的前面，现在就有两个元素排好序了，
我们再将没有排序的元素与排好序的元素列表进行比较，同样，如果小于第一个元素，就将
它插入到第一个元素前面，但是，如果大于第一个元素的话，我们就将它再与第2 个元素的
值进行比较，小于的话就排在第2 个元素前面，大于的话，就排在第2 个元素的后面。以此
类推，直到最后一个元素排好序。

 

点评：

     该算法在数据规模小的时候十分高效，该算法每次插入第K+1到前K个有序数组中
一个合适位置，K从0开始到N-1,从而完成排序


基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。排序过程：

 

 

 

public class InsertSorter<T extends Comparable<T>> extends Sorter<T> {


	/**
	 * 插入排序
	 */
	@Override
	public void sort(T[] array, int from, int len) {
		
		 T tmp=null;
         for(int i=from+1;i<from+len;i++)
         {
             tmp=array[i];
             int j=i;
             for(;j>from;j--)
             {
                 if(tmp.compareTo(array[j-1])<0)
                 {
                     array[j]=array[j-1];//把大值后移
                 }else
                	 break;//前面默认已经排好序
                
             }
             array[j]=tmp;//保存被替换的的值，进入下一个循环
         }
   }


	/**
 * 测试	
	 * @param args
	 */
	public static void main(String[] args) {
		Integer array[] = {2,35,5,78,1,90,13,56} ;
		for (int i = 0 ; i<array.length ; i++){
			System.out.print(array[i]+",");
		}
		System.out.println();
		Sorter sorter = new InsertSorter<Integer>() ;
		sorter.sort(array) ;
			
		for (int i = 0 ; i<array.length ; i++){
			System.out.print(array[i]+",");
		}				
		}
}

 

2、折半插入排序

在直接插入排序中，为了找到插入位置，采用了顺序查找的方法。为了提高查找速度，可以采用折半查找，这种排序称折半插入排序。

3、2－路插入排序

为减少排序过程中移动记录的次数，在折半插入排序的基础上加以改进：