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

Question

插入排序：对于随机排列长度为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是数组大小。这个效率是如何计算出来的？

Answer 1

Question 1:
Prerequisite knowledge:
The sum of the first n terms of the arithmetic sequence

Insertion sorting starts from the 2nd element. During the insertion process, it can be seen that the worst case is reverse sorting. It needs to be executed 1+2+3+...+n-1 times in total. According to the sum of the first n items, the result is (n -1)n/2 is approximately equal to n^2/2, similar questions can be found here.

Question 2:
Prerequisite knowledge:

1. Calculation of algorithm complexity of insertion sort (i.e. above)

2. Understanding of Shell Sort
   The defined increment of h here is 3. There is no mandatory requirement. The increment of h can also be 2

Example:

Note: When the increment is 2, the two arrays [72,874,283,911,820] and [401,141,592,887,348] are all inserted and sorted.

Question 3:
Prerequisite knowledge: number theory
详见<数据结构与算法分析_JAVA语言描述>定理7.4:

Rookie summary, a big pat.