【数据结构】排序（1）——直接插入排序希尔排序

一、直接插入排序

1.1、基本思想与分析

直接插入排序是⼀种简单的插入排序法。其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到⼀个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

实际上，与我们平时玩扑克牌🃏类似。

由基本思想我们可以推出直接插入排序的算法原理：
当我们准备插入第 i(i>=1) 个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…array[0]的排序码依次进行比较，直到找到插入位置，再将 array[i] 插入，原来位置上的元素均顺序后移。更加直观的图解如下：建议读者自行画图，加深理解🎨

1.2、代码实现💻

// 直接插入排序voidInsertSort(std::vector<int>&v){for(inti=0;i<v.size()-1;i++){intend=i;// 有序数组中最后一个元素inttmp=v[end+1];// 要插入进有序数组的元素while(end>=0){if(v[end]>tmp){v[end+1]=v[end];end--;}elsebreak;}v[end+1]=tmp;}}

1.3、时间复杂度分析

我们以排升序为例：

考虑最坏的情况，不难看出这是一个O(n^2)的时间复杂度。
当数组有序的时候，即最好的情况下时间复杂度为O(n)。

结论：元素集合越接近有序，直接插入排序算法的时间效率越高。

1.4、优化方案

这么一看，直接插入排序还是有着很大的优化空间。

那么，我们能否优化直接插入排序，使得时间复杂度尽量接近O(n)呢🧐？？

• 如果小的数据能够尽量在前，而大的数据尽量在后，在进行插入的时候是不是就能够减少数据的比较次数！！相反，当大的数据在前，小的数据在后，数据的比较次数就大大地增加了。
  因此，我们的优化方案就可以朝着这个方向进行——小的数据尽量在前，大的数据在后。而接下来我们所讲的希尔排序，就是最终的优化结果

二、希尔排序🌟🌟

2.1、基本思想与分析

希尔排序法又称为缩小增量法。希尔排序法的基本思想是📖：
先选定一个整数（通常是gap = n/3+1），把待排序数组所有元素分成各组，所有的距离相等的元素分在同一组内，并对每一组内的数据进行排序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进行插入排序，当gap=1时，就相当于直接插入排序。
它是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接插入排序算法的。

更加直观、详细的图解如下：建议读者自行画图，加深理解🎨

2.2、代码实现💻

代码实现与我们之前的步骤略有不同，并非是将每组视作一个独立的个体进行内部的排序，这样做的话则会有四层循环相互嵌套，导致代码异常丑陋。真正的希尔排序采用的是更加精妙的处理手段，具体代码如下⌨。

// 希尔排序voidShellSort(std::vector<int>&v){intn=v.size();intgap=n;while(gap>1){gap=gap/3+1;//保证最后一次绝对是1，当gap == 1时，则为希尔排序且时间复杂度为O(n)for(inti=0;i<n-gap;i++){intend=i;// 有序数组中最后一个元素inttmp=v[end+gap];// 要插入进有序数组的元素while(end>=0){if(v[end]>tmp){v[end+gap]=v[end];end-=gap;}elsebreak;}v[end+gap]=tmp;}}}

2.3、时间复杂度分析

希尔排序的时间复杂度不好计算，因为它的gap值并非一个固定值。对于同一个待排序数组，gap的不同，导致时间复杂度也会有所差异。《数据结构(C语言版)》——严蔚敏书中给出的时间复杂度为：

因此，我们可以感性地认为：希尔排序的时间复杂度以O(n^1.3)为主。

完🌅🌅🌅