详谈内部排序之希尔排序

希尔排序

---

基本思想：

​ 先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

技巧：

​ 子序列的构成不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个子序列,让增量dk逐趟缩短（例如依次取5,3,1），直到dk＝1为止。

优点：

​ 让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。

---

希尔排序的过程：

如上图所示，我们根据增量来取两个值来进行比较大小，循环一遍之后，就将增量减小，直到增量为1后停止减小。

例题：

例：关键字序列 T=(49, 38, 65, 97, 76, 13, 27, 49*, 55, 04) 请写出希尔排序的具体实现过程。 上面的表格就是每次循环完成的结果 ，下面我们来详细的解释每一个步骤。

希尔排序主要算法描述：

void ShellInsert ( SqList &L, int dk ) { //一趟希尔插入排序 //1.前后记录位置的增量是dk； //2.L.r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到 for (i=dk+1; i<=L.length; ++i ) if ( L.r[i].key< L.r[i-dk].key) {//将R[i]插入有序增量子表 L.r[0] = L.r[i]; // 暂存在R[0] for (j=i-dk; j>0 && (L.r[0].key< L.r[j].key);j -= dk) L.r[j+dk] = L.r[j]; // 记录后移，查找插入位置 L.r[j+dk] = L.r[0]; // 插入 } }//ShellInsert void ShellSort (SqList &L, int dlta[ ], int t) { // 按增量序列dlta[0..t-1]对顺序表L作希尔排序 for (k=0; k<t; ++k) ShellInsert( L, dlta[k]); // 一趟增量为dlta[k]的插入排序 } // ShellSort

希尔排序算法分析：

​ 开始时dk 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，dk 值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。

​ 希尔排序的时间复杂度较直接插入排序低。希尔排序的分析是一个复杂的问题，因为它的时间是和所取“增量”序列的函数密切相关。

​ 增量序列可有各种取法，但需注意应使增量序列中的值没有除1之外的公因子,并且最后一个增量值必须等于1。其分析是一个复杂的过程，因为它的时间是取“增量”序列的函数，这涉及一些数学问题尚未解决，因此，到目前为止，还没有求得一个组好得增量序列，但有大量的局部结论。

​ 对特定的待排序对象序列，可以准确地估算关键码的比较次数和对象移动次数。但想要弄清关键码比较次数和对象移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。

​ Knuth利用大量的实验统计资料得出，当n很大时，关键码平均比较次数和对象平均移动次数大约在 n1.25 到 1.6n1.25 的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。

希尔排序的性能分析：

时间效率：O(n(log2n)^2) ——所选增量比较合理

空间效率： O(1) —— 因为仅占用1个缓冲单元

算法的稳定性：不稳定