希爾排序對於h有序數組排序的選擇問題？

經檢查，確實是我的代碼錯誤，正確的代碼應當是exch(a,j,j-h),而不是exch(a,j,i)。

改正後，在100000個double數據下，shell比shell1快200倍左右。

原題目繼續保留，警示下自己一定要仔細，注意細節。

**********************************************************

我在《演算法》第四版看到的代碼如下：

public 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, i);
}
}
h /= 3;
}
}


對於第一個for循環的i++,我的理解是對於數組的每個元素所在的h間隔的數列都要進行插入排序.於是我將代碼改成如下所示:

public 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 += h) { for (int j = i; j &>= h less(a[j], a[j - h]); j -= h) {
exch(a, j, i);
}
}
h /= 3;
}
}


i++變成i+=h,這樣子對於h實際上只對數組中的間隔為h的一個序列進行了插入排序,我發現這樣子的速度有了更大的提升:

For 5000000 random Doubles
Shell1 is 17.903 times faster than Shell


其中shell1為我更改後的希爾排序.

請問為什麼會發生這樣的現象,我這種速度更快是特例還是有具體原因?

(我用的是surface pro3,intellij運行)

謝邀

首先你沒貼出來exch實現是啥，exch的位置應該是對a[j]和a[j-h]進行交換，跟i沒有任何關係，如果是對a[i]和a[j]交換，我的測試是失敗的，不能正常排序，所以最好先檢查下執行是否成功

其次，如果你每次i+=h，則實際上每輪只是對i為h的倍數的位置進行一次間隔的插入排序，無法實現快速減少逆序數的效果，所以懷疑你時間統計的代碼（你也沒貼出來），而我的測試，是你上面Shell的比你改的Shell1快300倍，用15w個double，如果是500w那Shell1跑個幾天都出不來的

代碼最好貼全了，很多時候是你用錯誤的測試方式得到了錯誤的結果

最後反對一下上面陳碩的回答，第一，不管題主是什麼動機研究shell排序，他問的只是這方面的技術問題，就算要提醒學習方式也可以在回答之後進行，第二，希爾排序在大規模數據下速度還是很快的，雖然大體上比不上快排，但複雜度是亞二次的（序列選好的話可以到O(N^1.167)），而且空間複雜度O(1)，是一種實用排序法，第三，內部排序而言，歸併由於要消耗O(N)空間，反倒是不太常用，雖然Python之類的sort實現用到

Shell 排序不是一個實用的排序演算法， 不必深究。

1. 快速排序
2. 插入排序
3. 堆排序
4. 歸併排序

哈哈，我和題主在看同一本書。今天正好學習到了希爾排序。我來談談我的理解。

1. 插入排序的優點是，對於基本有序的序列，可以很快地完成排序。特別地，對於已經排序好的序列進行插入排序，所需時間與序列長度n成正比。
2. 插入排序的缺點是，對於亂序的序列，花費的時間要多得多。特別地，對於逆序的序列進行插入排序，所需時間與序列長度n的平方成正比。
3. 希爾排序是插入排序的改進版本。
4. 希爾排序將大序列分成了h個小序列，小序列中的相鄰元素，在大序列中序號相差h。分別對每個小序列進行插入排序。
5. 小序列的插入排序時，小序列相鄰元素的交換位置，實際上是大序列中序號相差h的兩個元素的交換位置。實現遠距離元素交換位置，是希爾排序對插入排序的關鍵改進。
6. 隨著h的減小，每個元素都越來越靠近自己的位置。
7. 當h=1時，最後一個i和j的循環，實際上就是一個大序列的插入排序。這時的大序列已經是基本有序的了。正好可以發揮插入排序的優勢。

題主可以看看基維百科上的希爾排序介紹。https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F

回到問題，當把 i++改成了i+=h的時候，發生了什麼呢？

修改後，每次h循環，只對h個小序列中的包含0號元素的那一個小序列進行了插入排序。其餘的都沒有進行處理。導致了在h=1循環的時候，大序列沒有達到基本有序的狀態。絕大部分排序工作是在h=1循環中完成的。

以上。