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

目录一、直接插入排序1.1、基本思想与分析1.2、代码实现1.3、时间复杂度分析1.4、优化方案二、希尔排序2.1、基本思想与分析2.2、代码实现2.3、时间复杂度分析一、直接插入排序1.1、基本思想与分析直接插入排序是⼀种简单的插入排序法。其基本思想是把待排序的记录按其关键码值的大小逐个插入到⼀个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。实际上与我们平时玩扑克牌类似。由基本思想我们可以推出直接插入排序的算法原理当我们准备插入第 i(i1) 个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…array[0]的排序码依次进行比较直到找到插入位置再将 array[i] 插入原来位置上的元素均顺序后移。更加直观的图解如下建议读者自行画图加深理解1.2、代码实现// 直接插入排序voidInsertSort(std::vectorintv){for(inti0;iv.size()-1;i){intendi;// 有序数组中最后一个元素inttmpv[end1];// 要插入进有序数组的元素while(end0){if(v[end]tmp){v[end1]v[end];end--;}elsebreak;}v[end1]tmp;}}1.3、时间复杂度分析我们以排升序为例考虑最坏的情况不难看出这是一个O(n^2)的时间复杂度。当数组有序的时候即最好的情况下时间复杂度为O(n)。结论元素集合越接近有序直接插入排序算法的时间效率越高。1.4、优化方案这么一看直接插入排序还是有着很大的优化空间。那么我们能否优化直接插入排序使得时间复杂度尽量接近O(n)呢如果小的数据能够尽量在前而大的数据尽量在后在进行插入的时候是不是就能够减少数据的比较次数相反当大的数据在前小的数据在后数据的比较次数就大大地增加了。因此我们的优化方案就可以朝着这个方向进行——小的数据尽量在前大的数据在后。而接下来我们所讲的希尔排序就是最终的优化结果二、希尔排序2.1、基本思想与分析希尔排序法又称为缩小增量法。希尔排序法的基本思想是先选定一个整数通常是gap n/31把待排序数组所有元素分成各组所有的距离相等的元素分在同一组内并对每一组内的数据进行排序然后gapgap/31得到下⼀个整数再将数组分成各组进行插入排序当gap1时就相当于直接插入排序。它是在直接插入排序算法的基础上进行改进而来的综合来说它的效率肯定是要高于直接插入排序算法的。更加直观、详细的图解如下建议读者自行画图加深理解2.2、代码实现代码实现与我们之前的步骤略有不同并非是将每组视作一个独立的个体进行内部的排序这样做的话则会有四层循环相互嵌套导致代码异常丑陋。真正的希尔排序采用的是更加精妙的处理手段具体代码如下⌨。// 希尔排序voidShellSort(std::vectorintv){intnv.size();intgapn;while(gap1){gapgap/31;//保证最后一次绝对是1当gap 1时则为希尔排序且时间复杂度为O(n)for(inti0;in-gap;i){intendi;// 有序数组中最后一个元素inttmpv[endgap];// 要插入进有序数组的元素while(end0){if(v[end]tmp){v[endgap]v[end];end-gap;}elsebreak;}v[endgap]tmp;}}}2.3、时间复杂度分析希尔排序的时间复杂度不好计算因为它的gap值并非一个固定值。对于同一个待排序数组gap的不同导致时间复杂度也会有所差异。《数据结构(C语言版)》——严蔚敏书中给出的时间复杂度为因此我们可以感性地认为希尔排序的时间复杂度以O(n^1.3)为主。完