希尔排序

Author Avatar
Brian Lee 8月 05, 2018
  • 在其它设备中阅读本文章

《Algorithm》(Sedgewick)笔记:希尔排序


原理

  • 改进了插入排序,交换不相邻的元素以对数组的局部进行排序,并最终用插入排序将局部有序的数组排序
  • 希尔排序的思想是使数组中任意间隔为h的元素都是有序的,这样的数组被称为h有序数组。换句话说,一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组

复杂度

时间复杂度

不超过$O(n^2)$ ,当$n$ 较大时,比较和移动次数约在$n^{1.25}$ 到$1.6n^{1.25}$

空间复杂度

$O(1)$


图示

希尔排序


代码

public static void sort(Comparable[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3)
            h = 3 * h + 1;
        while (h >= 1) {
            //分别进行插入排序
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h)
                    exch(a, j, j - h);
            }
            h = h / 3;
        }
    }

上述代码使用了序列$\frac{1}{2}(3^k-1)$ ,从$N/3$ 开始递减至$1$

序列计算:

$h_{k+1}=3\times h_k+1 (h_1=1)$

$h_{k+1}+\frac{1}{2} = 3(h_k+\frac{1}{2})$

$\therefore h_k+\frac{1}{2}= \frac{3}{2}\times 3^{k-1}$

$\therefore h_k=\frac{1}{2}(3^k-1)$


特点

  • 希尔排序更高效的原因是它权衡了子数组的规模和有效性
  • 时间复杂度取决于N与增量序列
  • 如何选择最佳增量序列,目前尚未解决,但最后一个增量值必须为1,且避免增量序列中的值(尤其是相邻的值)有公因子

源码

https://github.com/XutongLi/Algorithm-Learn/blob/master/src/S2_Sorting/S2_1_6_ShellSort/ShellSort.java


本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
本文链接:http://brianleelxt.top/2018/08/05/shellsort/