一、认识插入排序
插入排序的思想其实很好理解，比如说学生按照身高排位置。前N-1个同学是有序的，那么第N个同学就一个一个从低到高比较，找到合适的位置插入即可。
斗地主的时候我们洗牌，就是根据大小插入或者是选择出什么牌，下面我们使用一张动图来演示一下什么是插入排序：链接
注意：
黄色部分：已经排好序的元素青色部分：将要排序的元素底部红色：正在排序的元素
二、代码实现
说实话插入排序的改进还是有很多种方式的，我们从最简单的插入排序出发，介绍几个；
我们在正式介绍每一种之前，看一个工具方法，用于展示数组元素。
public static void display(int[] arr) { for(int i=0;i<arr.length;i++) { System.out.print(arr[i]+" "); } };
1、普通插入排序方法
public static void insertOne(int[] array) { int counter = 1;//记录下来每一轮 for (int i = 1; i < array.length; i++) { // temp:表示待排序的元素，也就是动图中青色部分的元素。 int temp = array[i]; int insertPoint = i - 1; // 当前元素比待排序元素temp大 while (insertPoint >= 0 && array[insertPoint] > temp) { // 当前元素后移一位，留出来地方给temp插入 array[insertPoint + 1] = array[insertPoint]; insertPoint--; } array[insertPoint + 1] = temp; // 找到了插入位置，插入元素 display(array,counter); counter++; } }
这就是最简单的插入排序，我们可以发现，每次找插入位置的时候我们都要从头到尾一个一个比较。当数据量大的时候我们肯定不允许。于是我们换一种想法。使用我们之前学过的一种二分法查找的思想，使用二分法查找应该插入的位置。
2、二分插入排序方法
public void insertTwo(int[] array){ int counter = 1; for(int i=1;i<array.length;i++){ int temp = array[i]; if(array[i-1]>temp){ //使用二分法获取应插入位置的下标 intinsertIndex = binarySearch(0, i-1, temp); for(int j=i;j>insertIndex;j--){ array[j]= array[j-1]; } array[insertIndex]= temp; } display(); counter++; } }
我们看一下二分查找是如何找到应该插入位置的下表的。
public int binarySearch(int lowerBound,int upperBound,int target){ int curIndex; while(lowerBound<upperBound){ curIndex= (lowerBound+upperBound)/2; if(array[curIndex]>target){ upperBound= curIndex - 1; }else{ lowerBound= curIndex + 1; } } return lowerBound; }
这种情况，的确很优秀。不过我们有没有发现，我们在找插入位置的时候时间效率的确提高了，但是空间效率却没有提高，因为每次找到位置之后，我们都需要对插入位置其后面的元素往后移动一下，留出来这个位置。那么在空间上就需要很大的一块。我们再换一种思路，每次移动元素的时候，新开辟一个空间，用作移动元素的空间。
3、二路插入排序方法
public void insertThree(int[] array){ int [] newArray = new int [array.length]; newArray[0]= array[0]; //将原数组的第一个元素作为枢纽元素 int first = 0; //指向最小元素的指针 int last = 0; //指向最大元素的指针 //打印初始化数组 for(int j=0;j<newArray.length;j++){ System.out.print(newArray[j]+"\t"); } //开始排序 for(int i=1;i<array.length;i++){ //大于等于最大元素，直接插入到last后面，不用移动元素 if(array[i]>= newArray[last]){ last++; newArray[last]= array[i]; } //小于最小元素，直接插到first前面，不用移动元素 else if(array[i] < newArray[first]){ first= (first-1+len) % len; newArray[first]= array[i]; } //在最大值与最小值之间，且大于等于枢纽元素，插入到last之前，需要移动元素 else if(array[i] >= newArray[0]){ int curIndex = last; last++; do{ newArray[curIndex+1]= newArray[curIndex]; curIndex--; }while(newArray[curIndex]>array[i]); newArray[curIndex+1]= array[i]; } //在最大值与最小值之间，且小于枢纽元素，插入到first之后，需要移动元素 else{ int curIndex = first; first= (first-1+len) % len; do{ newArray[curIndex-1]= newArray[curIndex]; curIndex= (curIndex+1+len)%len; }while(newArray[curIndex]<=array[i]); newArray[(curIndex-1+len)%len]= array[i]; //插入到正确的位置 } display(newArray); }//for循环结束 }
上面这种方法代码很长，但是时间和空间效率的确高了很多。其实还有很多其他插入排序的改进，比如说希尔排序。在这里就先不讲了，我们下面来分析一下这个插入排序：
三、分析插入排序
插入排序我们只分析第一种最简单的插入排序。分析插入排序也是要分两种情况:
1、在最坏情况下，数组完全逆序
这时候插入第2个元素时要考察前1个元素，插入第3个元素时，要考虑前2个元素，以此类推，插入第N个元素，要考虑前 N - 1 个元素。因此，最坏情况下的比较次数是 1 + 2 + 3 + ... + (N - 1)，结果为 N^2 / 2，所以最坏情况下的复杂度为 O(N^2)。
2、最好情况下，数组已经是有序
这时候每插入一个元素，只需要考查前一个元素，因此此时插入排序的时间复杂度为O(N)。
