前言
希尔排序是 Donald Shell 于 1959 年提出来的一种排序算法, 它是第一批突破 这个时间复杂度的算法之一. 大话数据结构对这个算法的讲解, 我看得一知半解的, 之后网上找了下资料, 发现维基百科对这个算法的讲解非常不错, 特在此整理一波.
原理
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率
但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位
先上个维基百科的动图, 不知道你们看不看得懂, 反正我不是很懂......
说说我的个人理解:
希尔排序其实就是直接插入排序的升级, 原理就是先将整个待排序列按照某个增量 (也称步长) 分割成若干个子序列分别进行直接插入排序, 然后合并, 之后依次缩小增量大小在进行排序, 当增量足够小 (通常为 1) 时, 再对全体元素进行直接插入排序, 而此时需排序的数据几乎是已排好的了, 所以此时插入排序较快.
当然如果你觉得文字比较乏味就看下面的这些例子吧
例如, 假设有这样一组数[9 1 5 8 3 7 4 6 2], 如果我们先以步长为 4 进行分割, 就是这样:
- 9 1 5 8
- 3 7 4 6
- 2
然后我们对每列进行排序(注意每列哦):
- 2 1 4 6
- 3 7 5 8
- 9
将上述四行数字, 依序合并我们得到:[ 2 1 4 6 3 7 5 8 9 ]. 此时 2 已经往前移, 而 8,9 已经在后两位, 然后再以 2 为步长进行分割:
- 2 1
- 4 6
- 3 7
- 5 8
- 9
继续排序:
- 2 1
- 3 6
- 4 7
- 5 8
- 9
合并得到[ 2 1 3 6 4 7 5 8 9], 此时序列已经基本有序, 需交换数据的情况大为减少, 这时整列进行直接插入排序效率就非常高.
最终完成排序过程, 也就是步长为 1 时, 得到最终序列为: 1 2 3 4 5 6 7 8 9.
示例代码(C)
- #include <stdio.h>
- #define MAXSIZE 100 // 用于要排序数组的最大值
- typedef struct // 定义一个顺序表结构
- {
- int r[MAXSIZE+1]; // 用于存储要排序数组, r[0]用作哨兵或者临时变量
- int length; // 用于存储顺序表的最大长度
- }SqList;
- void ShellSort(SqList *L)
- {
- int i,j;
- int gap=L->length; // 获取数组长度
- for(gap/=2;gap>=1;gap/=2) // 步长
- for(i=gap+1; i<=L->length; i++) // 从第 gap+1 个元素开始, 因为 r[0]被当做临时变量
- if(L->r[i] <L->r[i-gap]) // 每个元素与自己组内的数据进行直接插入排序
- {
- L->r[0]=L->r[i]; // 把要交换的数据暂存的 L->r[0]中
- for(j=i-gap; j>0&&L->r[j]> L->r[0]; j-=gap)
- L->r[j+gap] = L->r[j]; // 记录后移, 查找插入位置
- L->r[j+gap]=L->r[0]; // 插入
- }
- }
- int main()
- {
- int i=0;
- int array[] = {39,80,76,41,13,29,50,78,30,11,100,7,41,86};
- SqList L;
- L.length = sizeof(array)/sizeof(array[0]); // 获取数组长度
- for(i=0;i<L.length;i++)
- {
- L.r[i+1]=array[i]; // 把数组存入顺序表结构
- }
- ShellSort(&L);
- // 输出排序后的数组
- for(i=0;i<L.length;i++)
- {
- printf("%d",L.r[i+1]);
- }
- return 0;
- }
可能有几个步骤略难懂, 这里解释下:
第 17 行: 这里的步长采用, 最终判断条件为 gap>=1, 这里不管你数组初始长度为多少, 除到最后均会等于 1, 而等于 1 时, 就是执行最后一次循环, 这个时候也就是所有元素进行直接插入排序. 当然也可写成 gap>0.
第 18 行: 在前面定义顺序表结构时, 我们加多了一位, 也就是把 r[0]当做交换数据时的临时变量.
第 22~23 行: 对于这个循环我们直接拿上面的例子中的一列进行讲解(9 3 2):
当 时, 9 和 3 进行了一次交换, 变为 (3 9 2)(位置为 1 5 9), 之后在 时, 做出的交换如上图所示(图略差...), 分为三个步骤:
第一次进入循环, 此时该列数值变为(3 9 9);
继续第二次循环, 此时变为(3 3 9);
跳出循环(注意: 跳出循环时多执行了一次), 执行
, 最终变为(2 3 9).
步长 (增量) 选择
步长的选取非常关键, 但是步长的选择没有统一规定, 也没绝对的规律. 只要满足最后一个步长为 1 即可. Donald Shell 最初建议步长选择为 , 虽然这样去可以比 类的算法更好, 但仍然有减少平均时间和最差时间的余地. 维基百科给出的部分步长与最坏情况下复杂度有:
已知的最好步长序列是由 Sedgewick 提出的 (1, 5, 19, 41, 109,...), 该序列的项来自 和这两个算式. 这项研究也表明 "比较在希尔排序中是最主要的操作, 而不是交换." 用这样步长序列的希尔排序比插入排序要快, 甚至在小数组中比快速排序和堆排序(后续博客整理), 但是在涉及大量数据时希尔排序还是比快速排序慢.
来源: https://juejin.im/post/5c18dc0df265da61461e1996