插入排序:对于随机排列长度为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是数组大小。这个效率是如何计算出来的?
問題一:![](http://img.php.cn/upload/image/000/000/000/f5a789571917ba8528d6d0a8d268eb2b-0.png)
前提知識:
等差數列前n項和
插入排序是從第2元素開始插入排序,插入過程,可知最壞情況就是逆排序,一共要執行1+2+3+...+n-1次,根據前n項和結果為(n -1)n/2約等於n^2/2,類似問題可見此處.
問題二:
前提知識:
插入排序的演算法複雜度的計算(即上)
希爾排序(shell sort)的理解
此處h的定義增量為3,沒有任何強制要求,h的增量也可以是2
範例:
注意:增量為2時,是對[72,874,283,911,820]跟[401,141,592,887,348]兩組數組全進行插入排序.
問題三:
![](http://img.php.cn/upload/image/000/000/000/03a13a032917e00ec3dd40266e59f285-2.png)
前提知識:數論
详见<数据结构与算法分析_JAVA语言描述>定理7.4:
菜鳥總結,大手輕拍.