一，前言

排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减地排列起来的操作。而对于一个排序算法而言，我们通常会从以下三个方面分析其性能：

• 稳定性：假设待排序序列中存在多个重复值，若是经过排序后，重复值之间的相对位置不变，则称这个排序算法是稳定的，否则就是不稳定。
• 时间复杂度：代码执行次数随n的增长趋势，通常使用大O的渐进法表示
• 空间复杂度：额外存储随n的增长趋势，其中递归算法空间=递归栈的最大深度，通常使用大O渐进表示法

常见的基于比较的排序算法有七种，对于这七种排序算法，又因其实现方式不同划分为以下四类：

• 插入排序：直接插入排序、希尔排序
• 选择排序：选择排序、堆排序
• 交换排序：冒泡排序、快速排序
• 归并排序：归并排序

本节内容主要讲解插入排序，并且都是以排升序为例进行讲解。

二，直接插入排序

1，算法思想

直接插入排序是一种简单的插入排序法，其基本思想是：

当插入第i（i>=1）个元素时，前面的array[0]，array[1]...array[i-1]已经排好序，此时用array[i]与前面已排好序的数据进行比较，找到合适位置将其插入，将插入位置及以后的元素依次后移一位。

2，算法特性

当待排序序列越趋于有序时，比较次数越少，排序效率越高。

时间复杂度：

• 最好情况：O(N)，待排序序列已经有序，每次只需比较一次
• 最坏情况：O(N^2)，序列完全逆序
• 平均情况：O(N^2)

空间复杂度：O(1)

稳定性：稳定

3，排序过程演示

注：

由上演示也可得，相同元素在排序后相对位置不变，这便是稳定的排序算法。同时，稳定的排序算法会同时存在稳定和不稳定两种实现，并不是绝对的

4，算法实现

/** * 直接插入排序 * @param array 待排序序列 */ public static void insertionSort(int[] array) { if(array == null) return; int n = array.length; for(int i = 1; i < n; i ++) { // 记录本轮待插入元素 int key = array[i]; // 向前寻找插入位置，同时后移元素 int j = i - 1; while(j >= 0 && key < array[j]) { array[j + 1] = array[j]; j --; } // 出循环即找到插入位置，写入即可 array[j + 1] = key; } }

注意：

1，i从1开始，是因为默认第一个元素有序

2，内层循环条件为 key < array[j]，即找到第一个小于等于key的元素时停止（默认前面均有序，故key插入到此处一定有序），这样可以保证排序是稳定的；若是判断条件取等，则该排序就变为不稳定

三，希尔排序

1，算法思想

希尔排序又称为缩小增量排序，是基于直接插入排序的一种优化，其在排序前进行多轮预排序使得数据趋于有序，最后一轮再对整组数据进行直接插入排序，由于此时数据趋于有序，故速度大大提升。其实现方式是：

先选定一个整数gap表示同一组中元素之间的间距，再对按照间距gap分的每一组分别进行排序。重复前文操作，gap不断变小，最后为1，当gap为1时即是对整组数据进行排序，如下图所示：

2，算法特性

正式排序前执行多组预排序，可以显著改善直接插入排序在趋于逆序数据中的劣势。

时间复杂度：取决于增量序列。平均约 O(n^1.3)；若采用原始折半增量（n/2, n/4, …, 1），最坏为O(n²)；采用 Hibbard 增量最坏 O(n^1.5)，Sedgewick 增量最坏 O(n^1.3)。

空间复杂度：O(1)

稳定性：不稳定

因为相同的元素可能被分到不同增量组中，跨组移动后可能改变它们的相对次序

3，算法实现

/** * 希尔排序 * @param array 待排序序列 */ public static void shellSort(int[] array) { if(array == null) return; // 缩小增量排序 int gap = array.length / 2; while(gap > 0) { insertionSortByGap(array, gap); gap /= 2; } } /** * 按增量gap进行分组插入排序 * @param array 待排序序列 * @param gap 增量 */ private static void insertionSortByGap(int[] array, int gap) { int n = array.length; for(int i = gap; i < n; i ++) { int key = array[i]; // 内层向前寻找步长为gap，如此即可保证每次都是同组间排序 int j = i - gap; while(j >= 0 && key < array[j]) { array[j + gap] = array[j]; j -= gap; } array[j + gap] = key; } }

注：
上述代码中的insertionSortByGap()方法，其本质相当于交替插入排序，其并非是每次将同一组排序完，而是在不同组之间使用插入排序。当gap!=1时，外层循环每次步进都会切换到另一组，而内层循环每次步进gap则可以保证每次都在本组内操作。
也就是：代码实现并没有显式地把数组分成若干组，而是通过下标间隔gap直接对同组元素做插入排序。