关于插入排序算法的效率和希尔排序的理解问题

各位大大好，最近在自学算法，碰到了一点问题。来请求各位，还望各位不要嫌弃。

插入排序：对于随机排列长度为 N 且主见不重复的数组，平均情况下插入排序需要~N^2/4次比较以及~N^2/4。最坏情况下需要~N^2/2次比较和~N^2/2次交换。

第一个问题：想请教一下这个效率是怎么计算的？

希尔排序是基于插入排序所改进的算法。书上是这样描述的：中心思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组被称为 h 有序数组。也就是说，一个 h 有序数组就是 h 个互相独立的有序数组编织在一起组成一个数组。这样说我是能够理解的，但是它的代码有点令我难以理解。

//一些简单的通用性代码就不粘贴了，减少篇幅，以免各位看官看的烦
    public static void sort(Comparable[] a) {
        int n = a.length;

        // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ... 
        int h = 1;
        while (h < n/3) h = 3*h + 1; 

        while (h >= 1) {
            for (int i = h; i < n; i++) {、
                //less 是用来比较大小的， a[j]<[j-h]
                for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
                    //交换 a[j]和 a[j-h]的位置
                    exch(a, j, j-h);
                }
            }
            assert isHsorted(a, h); //判断是否有序的代码
            h /= 3;
        }
        assert isSorted(a);
    }

第二个问题是： h 这个递增序列是什么意思？它有什么作用？为什么是h=3*h+1？
第三个问题是：书上说最坏的情况是 N^(3/2)。 N 是数组大小。这个效率是如何计算出来的？

lecher

2016-09-14 22:39:39 +08:00

假设有一个数组长度为 N
for 循环遍历一次数组，时间复杂度就是 N
如果是嵌套两个 for 循环，时间复杂度就是 N^2
之后 for 循环内的循环剪枝可以优化掉的次数优化就得出你看到的最终复杂度，算法的书上第一章都会讲怎么算。
一楼建议的视频有完整的讲解推演，需要有一定的高等数学基础。看看补补基础，对实际分析问题，技术选型都有帮助。

Mistwave

2016-09-16 10:50:08 +08:00

@Adia 那我建议你重复看，自己写个例子，人肉逐行模拟代码。
至于你提的几个问题：
第一个，就是数次数，把长度为 N 的 list 进行一次插入排序，算法中进行的“两两比较”的次数和“两数交换”的次数，归纳出来是那么多。
第二个，这个循环是找一个最大的 h ， h<=n ，也就是找初始 h 值。至于为什么是 1/2(3^k-1)，书上也说了，这是一个简单的，且和复杂递增序列性能相近的选择。这里的重点是讲希尔排序的思想，而不是优化这个算法，所以这里就用这个序列凑合了。
第三个，不好意思，我没有看见这个结论，能说说是书上哪里给出的吗？
手机打字，有点乱，见谅。