直接插入排序

插入排序的思想有点类似抓扑克牌 ， 过程如下:

  • 从第一个元素开始，该元素可以看作已经排好序；
  • 取出下一个元素，从这个元素从后往前开始扫描，如果该元素大于新元素，将该元素移到下一位置；
  • 重复上述步骤，直到找到已排序的元素小于或者等于新元素的位置，将新元素插入到该位置后；
  • 注意插入排序和数据状况有关系，涉及到最好情况，最差情况和平均情况。
  • 插入排序在工程上，当数组元素个数少的时候用的多，因为如果数组比较有序的话，会很快；

image.png

代码:

  1. public static void insertSort(int[] arr) {
  2.     for (int i = 1; i < arr.length; i++) {
  3.         int temp = arr[i], j;
  4.         for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
  5.             arr[j + 1] = arr[j]; //中间的元素往后面移动
  6.         }
  7.         arr[j + 1] = temp;   //将key插入到合适的位置
  8.     }
  9. }

更加简单的做法，配上swap函数:(有点类似冒泡了):这里要注意第二层循环的下标j > 0。

  1. public static void insertSort2(int[] arr) {
  2.     for (int i = 1; i < arr.length; i++) {
  3.         for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--)
  4.             swap(arr, j, j - 1);
  5.     }
  6. }

折半插入排序

二分插入排序是对插入排序的一个小小的改进：

  • 改进的地方在于在前面已经排好序的序列中找当前要插入的元素的时候采用二分查找的方式去找那个插入的位置(大于key的那个位置) ，关于二分查找可以看这篇博客；
  • 找到那个位置之后，再进行元素的移动，已及把那个元素插入到找到的那个位置；

image.png

代码:

  1.  //二分插入排序
  2.     public static void insertSort3(int[] arr) {
  3.         int n = arr.length;
  4.         for (int i = 1; i < n; i++) {
  5.             int temp = arr[i];
  6.             int low = 0, high = i - 1;
  7.             while (low <= high) {
  8.                 int mid = low + (high - low) / 2;
  9.                 if (arr[mid] > temp) {
  10.                     high = mid - 1;
  11.                 } else {
  12.                     low = mid + 1;
  13.                 }
  14.             }
  15.             //二分结束之后　L = 刚好大于key(不是等于)的那个位置
  16.             for (int j = i - 1; j >= low; j--) {
  17.                 arr[j + 1] = arr[j];
  18.             }
  19.             arr[low] = temp;
  20.         }
  21.     }

希尔排序

希尔排序使更高效的插入排序，它的思想在于，

  • 把数组分成几块，每一块进行一个插入排序；
  • 而分块的依据在于增量的选择分好块之后，从gap开始到n，每一组和它前面的元素（自己组内的）进行插入排序；

每次和组内的元素比较完之后，最后的元素基本就是有序的了，希尔排序相对于插入排序的优势在于插入排序每次只能将数据移动一位，不过希尔排序时间复杂度的大小还是要取决于步长的合适度，另外希尔排序不是一种稳定的排序算法。
image.png

代码:

  1. //步长为n/2....
  2.  public static void shellSort2(int[] arr) {
  3.         for (int gap = arr.length; gap > 0; gap /= 2) {     //增量序列
  4.             for (int i = gap; i < arr.length; i++) {        //从数组第gap个元素开始
  5.                 int temp = arr[i], j;                        //每个元素与自己组内的数据进行直接插入排序
  6.                 for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap) {
  7.                     arr[j + gap] = arr[j];
  8.                 }
  9.                 arr[j + gap] = temp;
  10.             }
  11.         }
  12.     }
  14. //步长为 n*3+1
  15.   public static void shellSort(int[] arr) {
  16.         int gap = 0;
  17.         for (; gap <= arr.length; gap = gap * 3 + 1) ;
  18.         for (; gap > 0; gap = (gap - 1) / 3) { //增量序列
  19.             for (int i = gap; i < arr.length; i++) {  //从数组第gap个元素开始
  20.                 int temp = arr[i], j;  //每个元素与自己组内的数据进行直接插入排序
  21.                 for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap) {
  22.                     arr[j + gap] = arr[j];
  23.                 }
  24.                 arr[j + gap] = temp;
  25.             }
  26.         }
  27.     }