一文理清排序算法中的直接插入、快排和希尔排序的区别
前言
在上一篇文章中，给大家介绍了冒泡排序和选择排序，这两种算法都是排序算法。实际上排序算法还有插入、希尔、快速排序等，接下来我们就来学习一下这几种排序算法。
全文大约【5400】 字，不说废话，只讲可以让你学到技术、明白原理的纯干货！本文带有丰富的案例及配图视频，让你更好地理解和运用文中的技术概念，并可以给你带来具有足够启迪的思考......
一. 直接插入排序
1. 概念
直接插入排序(Insertion Sort) ，顾名思义就是把未排序的元素一个一个地插入到有序的集合中，插入时把有序集合从后向前扫一遍，找到合适的插入位置。 为了让大家更好地理解插入排序，通过一个简单的例子给大家解释一下插入排序的含义，我们以日常生活中的纸牌游戏为例：
一开始，上述纸牌是乱序状态的，我们想办法对上述纸牌进行排序操作。
(1) 第一次，将第一张牌8看做是已经排好序的牌，右边的5、3、9都是未排好序的。
(2) 第二次，将5插入到排好序的队伍中，5比8小，放到8的前面。
(3) 第三次，将3也插入到排好序的队伍中，3比5和8都小，所以放到5的前面。
(4) 第4次，将9也插入到排好序的队伍中，9比其他牌都大，所以放在最后。
经过以上几个步骤，这样所有的牌都排好序了。
2. 实现原理
插入排序的实现原理，其实就是将数列分成有序区间和无序区间两个部分。初始时，有序区间中只有一个元素，即数列的第一个元素。然后从无序区间取出一个元素，插入到有序区间的末尾，新插入的元素要与有序区间的数据一一比较大小。如果该数据大于有序区间的最后一个数据，则不交换位置，直接插入到有序区间的末尾即可。如果该数据小于有序区间的最后一个数据，则需要换位，换位后该数据还要与前一位数据继续比较大小，直到找到合适的位置才停止比较。
3. 实现步骤
根据上面的实现原理，再给大家梳理一下插入排序的实现步骤：
(1) 第1步：从数列的第2个元素开始抽取元素；
(2) 第2步：把它与左边的第一个元素进行比较，如果左边的第一个元素比它大，则继续与左边第二个元素比较下去，直到遇到小于等于它的元素，然后插到这个元素的右边。
(3) 第3步：继续选取第3、4....n个元素，重复步骤2，并选择适当的位置插入。
现在，我们可以通过一个实际的例子演示插入排序的过程。例如有一个待排序数组[5，8，6，3，9，2，1，7]，插入排序步骤如下：
(1) 初始时，有序区间中只有5，无序区间中有8、6、3、9、2、1、7。
(2) 将无序区间的第一个元素8插入到有序区间的数列末尾，8和5比较大小，8比5大则无需交换位置。此时有序区间中的元素是5、8，无序区间中有6、3、9、2、1、7。
(3) 将无序区间的第一个元素6插入到有序区间的末尾，形成5、8、6的排列顺序。6和左侧的8比较大小，6比8小则换位；6再与5比较，6比5大则无需换位。最后有序区间中形成了5、6、8的排列。此时，无序区间中还有3、9、2、1、7。
(4) 将无序区间的第一个元素3插入到有序区间的末尾，形成5、6、8、3的排列顺序。3和左侧的8比较大小，3比8小则换位；3再与6比较大小，3比6小则继续换位；3与5比较大小，3比5小继续换位。最后形成3、5、6、8的排列，此时，有序区间中是3、5、6、8，无序区间中还有9、2、1、7。
（5) 然后依次类推，直到无序区间为空时，排序结束。最终排序的结果为：1、2、3、5、6、7、8、9。
4. 编程实现
接下来我们使用Java语言，对插入排序算法进行编程实现：
public static void insertionSort(int[] arr) {
int loop = 0;
int count = 0;
//对数组进行遍历
for (int i = 0; i < arr.length; i++) {
//第二个循环仅仅是将当前数据跟自己左边的数字进行比较，如果小于左边数字则交换位置，否则位置不变。
for (int j = i; j > 0; j--) {
count++;
//此处使用break比使用if效率高，两者在比较次数上有差别。
if (arr[j] >= arr[j - 1]) break;
// 前后两个数据交换位置
arr[j] = arr[j] + arr[j - 1] - (arr[j - 1] = arr[j]);
}
}
}
5. 总结
接下来我们把插入排序的特性总结一下。
5.1 时间复杂度
根据给定的数列的混乱程度，时间复杂度可做如下分析：
(1) 当数列本身是有序的，插入排序的时间复杂度是O(n)。原因是如果数列本身是有序，插入排序需要将每相邻的两个数字各比较一次，总共比较n-1次， 所以时间复杂度是O(n)。
(2) 当数列是无序的，最坏的情况下需要比较n(n-1)/2次，所以时间复杂度是O(n2)。
5.2 空间复杂度
(1) 插入排序是原地排序，其空间复杂度是O(1)。
(2) 插入排序中，无序区间的元素在插入到有序区间的过程中，是依次与左侧的元素比较，如果两个元素相等，则不交换位置。
5.3 插入排序的适用场景
(1) 一个有序的大数组中融入一个小数组，比如有序大数组[1, 2, 3, 4, 5, 6, 7, 8, 9}中融入一个小数组[0, 1]。
(2) 数组中只有几个元素的顺序不正确，或者说数组部分有序。
总结来说，插入排序是一种比较简单直观的排序算法，适用于处理数据量比较小或者部分有序的数列。
二. 快速排序
1. 概念
快速排序(Quick Sort) ，其是对冒泡排序的一种改进，该算法由霍尔(Hoare)在1962年提出。与冒泡排序一样，快速排序也属于交换排序算法，通过元素之间的比较和交换位置来达到排序的目的。
快速排序每次排序的时候设置一个基准点，将小于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样每次交换的时候就不会像冒泡排序一样只能在相邻的两个数之间进行交换，交换的距离就得到提升。快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。这样总的比较和交换次数就少了，排序效率自然就提高了。
通过一趟排序，将要排序的数据分割成两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程递归进行，以此达到整个数据变成有序序列。快速排序算法的实现思路就是分治思想的应用。
2. 实现思路
快速排序基于递归的方式来实现，其实现思路如下：
(1) 选定一个合适的值(理想情况是选择数列的中值最好，但为了实现方便一般都是选择数列的第一个值)，称为“基准元素”(pivot)。
(2) 基于基准元素，将数列分为两部分，较小的分在左边，较大的分在右边。
(3) 第一轮下来，这个基准元素的位置一定在最终位置上。
(4) 对左右两个子数列分别重复上述过程，直到每个子数列中只包含一个元素则排序完成。快速排序的核心思想就是在给基准元素找正确的位置。
3. 实现步骤
接下来通过一个示例来讲解快速排序的步骤。
假设现在有一个乱序数组[5，8，6，3，9，2，1，7]，我们使用快速排序算法进行排序。首选要选择一个元素作为基准元素，在此例中，我们可以选择首元素5作为基准元素。接下来进行元素的交换，具体步骤如下：
(1) 选定基准元素5，同时设置两个指针分别为left和right，分别指向最左侧元素5、最右侧元素7。移动和比较的规则是：
从right指针的位置开始，让指针指向的元素和基准元素做比较。right指针指向的数据如果小于基准元素，则right指针停止移动；切换至left指针，否则right指针继续向左移动。
轮到left指针移动时，让left指针指向的元素与基准元素做比较。将left指针指向的数据和基准元素做比较。left指向的元素数据如果大于基准元素，则left指针停止移动，否则left指针继续向右移动。
将left和right指针指向的元素交换位置。
(2) right指针先开始，right指针当前指向的数据是7，由于7>5，right指针继续左移，指向到1，由于1<5，停止在1的位置。
轮到left指针。由于left开始指向的是基准元素5，所以left右移1位，指向到8。由于8>5，所以left指针停下
接下来，left和right指向的元素进行交换。此时形成数列为[5, 1, 6, 3, 9, 2, 8, 7]
(3) 重新切换到right指针，指针向左移动，right指针指向到2。由于2<5，right指针停止在2的位置。
轮到left指针，指针右移1位，指向到6，由于6>5，所以left指针停下。
接下来，left和right所指向的元素进行交换。此时形成数列为[5, 1, 2, 3, 9, 6, 8, 7]。
(4) 重新切换到right指针，指针向左移动。right指针指向到9，由于9>5，right指针继续左移，指向到3，由于3<5，则right指针停止在3的位置。
轮到left指针，指针右移1位，指向到3，此时right指针和left指针重叠在一起。
接下来，将pivot元素5与重叠点的元素3进行交换，此时形成数列为[3, 1, 2, 5, 9, 6, 8, 7]。第一轮排序结束。
我们把上述的文字描述过程，做成对应的示意图，如下所示：
第一轮排序结束后，本轮的基准元素5的位置，就是最终排序后所在的位置。接下来，我们采用递归的方式，分别对基准元素5左侧的前半部分[3, 1, 2]进行排序，再对元素5右侧的后半部分[9, 6, 8, 7]进行排序，如下图所示：
(1) 基准元素5的前半部分[3, 1, 2]，以3为基准元素，经过排序，结果为[2, 1, 3]。本轮下来，本轮的基准元素3的位置就是其最终位置。
(2) 上轮基准元素3左侧的队列[2, 1]，以2为基准元素排序，排序结果为[1, 2]。本轮下来，本轮的基准元素2的位置就是其最终位置。
(3) 上轮基准元素2左侧只剩下元素1，1就是自己的基准元素。这样元素1的最终位置就确定了。
(4) 基准元素5的后半部分[9, 6, 8, 7]，以9为基准元素进行排序，结果为：[7, 6, 8, 9]，本轮下来，本轮的基准元素9的位置就是其最终位置。
(5) 上轮基准元素9左侧的队列[7, 6, 8]，以7为基准元素进行排序，结果为[6, 7, 8]。本轮下来，本轮的基准元素7的位置就是其最终位置。
(6) 上轮基准元素7左侧只剩下6，6就是自己的基准元素。这样元素6的最终位置就确定了。
(7) 基准元素7右侧只剩下8，8就是自己的基准元素。这样元素8的最终位置就确定了。
(8) 此时基准元素5、3、2、1、9、7、6、8都找到其正确的位置，则排序结束。
4. 编码实现
接下来我们使用Java语言对快速排序算法进行代码实现：
public static void quickSort(int[] arr, int start, int end) {
// 递归结束条件:start大于或等于end时
if (start < end) {
// 得到基准元素位置
int pivotIndex = partition(arr, start, end);
// 根据基准元素，分成两部分进行递归排序
quickSort(arr, start, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, end);
}
}
private static int partition(int[] arr, int start, int end) {
// 取第1个位置的元素作为基准元素
int pivot = arr[start];
int left = start;
int right = end;
while (left < right) {
//right指针左移
while (left < right && arr[right] >= pivot) right--;
//left指针右移
while (left < right && arr[left] <= pivot) left++;
if (left >= right) break;
//交换left和right 指针所指向的元素
arr[left] = arr[left] + arr[right] - (arr[right] = arr[left]);
}
// 将基准元素与指针重合点所指的元素进行交换
arr[start] = arr[left];
arr[left] = pivot;
return left;
}
这里使用了两个方法quickSort和partition实现快速排序算法的逻辑，其核心思路与前文描述一致，先找到一个元素作为基准元素，然后再分开进行排序。
三. 希尔排序
1. 概念
希尔排序(Shell’s Sort) ，该算法是插入排序的一种，又称“缩小增量排序”(Diminishing Increment Sort) ，希尔排序是Shell在1959年提出的。
希尔排序是基于直接插入排序进行改进而形成的排序算法。 它是直接插入排序算法的一种更高效的改进版本。直接插入排序本身还不够高效，插入排序每次只能将数据移动一位。当有大量数据需要排序时，会需要大量的移位操作。但是插入排序在对几乎已经排好序的数据操作时，效率很高，几乎可以达到线性排序的效率。所以，如果能对数据进行初步排列达到基本排序，然后再用插入排序就会大大提高排序效率。希尔排序正是基于此思路而形成的。
2. 实现步骤
希尔排序的步骤简述如下：
(1) 把元素按步长gap分组，gap的数值其实就是分组的个数。gap的起始值为数列长度的一半，每循环一轮gap减为原来的一半。
(2) 对每组元素采用直接插入排序算法进行排序。
(3) 随着步长逐渐减小，组就越少，组中包含的元素就越多。
(4) 当步长值减小到1时，整个数据合成一组，最后再对这一组数列用直接插入排序进行最后的调整，最终完成排序。
我们以无序数列[5，8，6，3，9，2，1，7，,4]为例，详细介绍希尔排序的步骤：
(1). 第一轮排序，gap = length/2 = 4，即将数组分成4组。四组元素分别为[5，9，4]、[8，2]、[6，1]、[3，,7]。对四组元素分别进行排序结果为：[4，5，9]、[2，8]、[1，6]、[3，7]。将四组排序结果进行合并，得到第一轮的排序结果为：[4，2，1，3，5，8，6，7，9]。如下图所示。
(2). 第二轮排序，gap = 2，将数列分成2组。两组的元素分别是[4，1，5，6，9]和[2，3，8，,7]。这两个组分别执行直接插入排序后的结果为[1，4，5，6，9]和[2，3，7，8]。将两组合并后的结果为[1，2，4，3，5，7，6，8，9]，如下图所示。
(3). 第三轮排序，gap = 1，数组就变成了一组。 该组的元素是[1，2，4，3，5，7，6，8，9]，这个组执行直接插入排序后结果为[1，2，3，4，5，6，7，8，9]，这个结果就是第三轮排序后得到的结果。此时排序完成，如下图所示。
3. 编码实现
接下来我们用代码对希尔排序进行编程实现：
public static void shellSort(int[] arr) {
int loop = 0;
//增量gap，并逐步缩小增量
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//对一个步长区间进行比较 [gap,arr.length)
for (int i = gap; i < arr.length; i++) {
//对步长区间中具体的元素进行比较
for (int j = i - gap; j >= 0; j -= gap) {
//System.out.println("j=" + j);
if (arr[j] <= arr[j + gap]) break;
//换位
arr[j] = arr[j] + arr[j + gap] - (arr[j + gap] = arr[j]);
}
}
}
}
4. 总结
接下来我们再把希尔排序的复杂度等情况进行分析总结，如下：
(1) 希尔排序的时间复杂度与增量(即步长gap)的选取有关。例如，当增量为1时，希尔排序退化成了直接插入排序，此时最坏情况时间复杂度为O(n2)。而具有增量的希尔排序的平均时间复杂度为O(n^1.3)，希尔排序最好情况时间复杂度是O(n)。
(2) 希尔排序的空间复杂度是O(1)。
(3) 直接插入排序是稳定的，不会改变相同元素的相对顺序。 但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱。也就是说，对于相同的两个数，可能分在不同的组中而导致它们的顺序发生变化，所以希尔排序是不稳定的。
四. 结语
至此，我们我们已经向大家介绍了冒泡排序、选择排序、插入排序、快速排序、希尔排序等五种经典的排序算法。除此以外，还有堆排序、归并排序、桶排序、计数排序等一些经典的排序算法。
大家会发现，我们介绍排序算法的步骤和过程都是相同的，基本都包含算法概念、思想和原理、算法步骤，以及编码实现等几个部分。
在本篇的最后，我们给大家总结出经典的排序算法的对比和总结，我们从时间复杂度、空间复杂度、稳定性等几个方面进行横向总结。
| 排序算法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 |
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 插入排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 |
| 快速排序 | O(nlogn) | O(n2) | O(nlogn) | O(nlogn) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 希尔排序 | O(n^1.3) | O(n2) | O(n) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 桶排序 | O(n+k) | O(n2) | O(n) | O(n+k) | 稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 |
| 基数排序 | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | 稳定 |