1.插入排序简介
插入排序是一类借助“插入”进行排序的方法，其主要思想是：每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好。
插入排序的两个：直接插入排序 和 希尔排序
2.直接插入排序（straight insertion sort）
排序过程：
1.将所有记录分为两个区域：有序区 和 无序区。
2.将无序区的第一个记录插入到有序区的合适位置中。
3.重复执行2，直到无序区没有记录为止。
public class StraightInsertionSort { public static void main(String[] args) { int arr[] = { 2, 5, 3, 6, 4, 9, 8, 7, 1 }; insertsort(arr); System.out.println(Arrays.toString(arr)); } public static void insertsort(int[] arr) { int temp; // 从无序区第一个记录（下标为1） for (int i = 1; i < arr.length; i++) { temp = arr[i];//记录当前比较的数字 // 有序区的比较 int insertIndex = -1;//这是一个标识， 等于-1的时候表示不进行插入，大于-1的时候表示插入的位置 //这里主要是做一个有序区的记录位置移动 和 获得待排序记录需要插入位置(insertIndex) for (int j = i - 1; j >= 0 && arr[j] > temp; j--) { arr[j + 1] = arr[j]; insertIndex = j; } // 也就是说当上面的for循环执行的时候(也就是有序区中间出现了记录移动)，我们才需要将当前排序的数字插入到指定位置 if (insertIndex >= 0) { arr[insertIndex] = temp; } } } }
[1, 2, 3, 4, 5, 6, 7, 8, 9]
最好的情况：原本排序都是正序，那么只需要比较n-1次，记录移动0次，那么时间复杂度为O(n);
最差的情况：原本排序都是逆序，那么需要比较1+2+3+4+..+(n-1)次[(n-1)n/2] ，因为每一次比较都会移动一次记录所以记录移动也是[(n-1)n/2],时间复杂度为O(n的平方)
另外一提：直接插入算法是稳定算法
在insertsort这个方法中，外循环我们用了insertIndex 这个参数来记录无序区的值在有序区的插入位置。
然后我们可以发现 insertIndex 这个值和 内循环的 j 参数永远都是 offset -1的，于是可以修改成这样：
public static void insertsort(int[] arr) { int temp; // 从无序区第一个记录（下标为1） for (int i = 1; i < arr.length; i++) {//外循环 temp = arr[i];// 记录当前比较的数字 // 有序区的比较 int j; // 这里主要是做一个有序区的记录位置移动 和 j用来记录插入的位置(实际上j的位置永远都offset了-1 ) for (j = i - 1; j >= 0 && arr[j] > temp; j--) {//内循环 arr[j + 1] = arr[j]; } arr[j + 1] = temp;// 无论上面的for循环是否有执行，我们的j这个值永远都是比实际需要插入的下标少了-1 } }
3.希尔排序
在直接插入算法中我们发现1.待排序的序列如果基本有序的话，直接插入排序的效率很高 2.待排序的记录个数较少的时候效率也很高
(注意基本有序和局部有序是两个概念,基本有序比如：1，2，3，8，4，5，9，7，6，局部有序如：6，7，8，9，1，2，3，4，5。局部有序不能提升插入排序的效率)
那么希尔排序的基本思想就是：将待排序记录分割成若干个子序列，对每个子序列进行插入排序，待整个序列基本有序的时候，再对全体记录进行一次直接插入排序。
希尔算法具体详解请参考：
https://blog.csdn.net/qq_39207948/article/details/80006224
https://www.jianshu.com/p/40dcc3b83ddc
public static void shellSort(int[] arr) { // 每次增量为数组长度一半 int arrLength = arr.length; for (int gap = arrLength / 2; gap > 0; gap = gap / 2) { for (int i = gap; i < arrLength; i++) { // 将每组需要排序的子序列 的增量 和 无序区第一个开始的位置传过去 进行排序; insertS(arr, gap, i); } } } // 内部插入排序需要知道 增量gap 和 无序区的开始位置startIndex public static void insertS(int[] arr, int gap, int startIndex) { // 写法和直接插入排序应该是差不多的 int temp = arr[startIndex]; int j; // 无序区的比较 for (j = startIndex - gap; j >= 0 && arr[j] > temp; j = j - gap) { arr[j + gap] = arr[j]; } arr[j + gap] = temp; } public static void main(String[] args) { int arr2[] = { 2, 5, 3, 6, 4, 9, 8, 7, 1, 5, 6, 9, 8, 7, 4, 11, 23, 15, 85 }; shellSort(arr2); System.out.println(Arrays.toString(arr2)); }
[1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 11, 15, 23, 85]
希尔排序是一种不稳定的排序方法
原文：https://www.cnblogs.com/lvsafe/p/12495771.html