插入排序

 

       有一个已经有序的数据序列，要求在这个已经排好序的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法。

 

      插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。

 

      如下图所示：

 

 

        算法描述

        一般来说，具体算法描述如下：

       1.从第一个元素开始，该元素可以认为已经被排序

       2.取出下一个元素，在已经排序的元素序列中从前向后扫描

       3.如果该元素小于某个有序序列中的某个元素a，将该元素插入a之前，该元素以后元素后移

       4.重复步骤2~3 

 

       Java代码实现如下：

       

	private static void insertSort(int[] a){
		for(int i= 1;i<a.length;i++){
			for(int j = 0;j<i;j++){ //将a[i]插到有序数列a[0]~a[i-1]中,从前向后扫描；
				if(a[i]<a[j]){	
					backMove(j,i,a); //a[j]~a[i-1]中元素后移
					break;
				}
			}
			System.out.print("第"+ i +"趟插入排序：");
			print(a);
			System.out.println();
		}
		//插入排完序后；
		print(a);
	}

	private static void backMove(int start,int end,int[] a){
		int temp = a[end];
		for(int i = end;i>start;i--){
			a[i] = a[i-1];
		}
		a[start] = temp;
	}

	private static void print(int[] a) {
		for(int i:a)
			System.out.print(i+" ");		
	}

     

 

        该算法的变种：

        根据上述算法描述的第2步

        1.插入元素可以从数据的末尾开始取：

                  这样代码实现较容易些，但移动的元素较多；

        2.从已排好序的序列的下一个元素取，但从已排好的序列从后向前扫描。这样上述算法描述第3步就变成：如果该元素大于扫描的某个元素a，插入a元素之后；

       3.如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序（或者二分插入排序或者折半插入排序）。

            插入排序中，总是先寻找插入位置，然后在实行挪动和插入过程；寻找插入位置采用顺序查找的方式（从前向后或者从后向前），既然需要插入的数组已经是有序的，那么可以采用二分查找方法来寻找插入位置，提高算法效率，但算法的时间复杂度仍为O(n2)。

 

        根据以上变种总结：

              1.取插入的元素有两种方式：

                       （1）取下一个元素；

                       （2）取数列最后一个元素；

              2.扫描有序序列已获取插入元素的位置有三种方式：

                       （1）从前向后扫描；

                       （2）从后向前扫描；

                       （3）二分查找；

 

         一般插入方式为（1）（1），称为简单插入排序；优化插入方式为（1）（3），称为二分查找排序（二分查找排序即二分插入排序，实质即插入思想）。

 

          算法复杂度

            通过以上代码，很容易知道，时间复杂度度为O(n^2)。是稳定排序。