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

질문 1:
전제 지식:
등차수열의 처음 n항의 합

삽입정렬은 2번째 요소부터 시작되는데, 삽입과정에서 최악의 경우는 역정렬을 총 1+2+3+...+n-1회 수행해야 함을 알 수 있다. 처음 n개 항목의 합에 따르면 결과는 (n-1)n/2가 대략 n^2/2와 같습니다. 여기에서 비슷한 질문을 찾을 수 있습니다.

질문 2:
전제 지식:

1. 삽입 정렬의 알고리즘 복잡도 계산(예: 위)

2. 쉘 정렬의 이해
   여기서 h의 정의 증가분은 3입니다. h의 증가분은 2일 수도 있습니다.

예:

참고: 증분이 2이면 두 배열 [72,874,283,911,820]과 [401,141,592,887,348]이 모두 삽입되고 정렬됩니다.

질문 3:
전제 지식: 정수론
详见<数据结构与算法分析_JAVA语言描述>定理7.4:

신인 요약, 대박