一、概述
謝耳排序法是基於插入排序法的變化型，若讀者不了解，建議先認識一下會比較好。
插入排序法的缺點是每一輪操作只能排好一項資料，且伴隨大量的資料搬移，甚至只能移動一個位置。而謝耳排序法是具有「間隔」（gap）的插入排序法。它每一輪操作的主要目的並不是排序，而是利用間隔，試圖在搬移資料時加大腳步，早點到達正確的位置附近。
直到最後一輪操作，間隔將等於1，相當於普通的插入排序法。此時在資料趨近於排序完的情況下，最後一輪的效率會更好。
二、排序過程
假設我們有一些數值資料：6、8、2、3、4、7、5、1、9，數量為9個。在第一回合，首先令「間隔」（gap）為資料數量的一半，也就是4（捨棄小數點）。
接著從第一項開始，針對間隔為4的資料做插入排序法。舉例來說，此處參與的資料為6、4、9，會被排成4、6、9後放到對應位置。讀者可參考下圖第一、二列。
接著再從第二項開始，以相同的間隔做插入排序法，此處參與的資料為8、7。依此類推，最後會以間隔前的最後一項（即第四項）為起點做相同處理，完成後便結束該回合。排序結果為：4、7、2、1、6、8、5、3、9。
第二回合的排序，會讓間隔縮減為上回合的一半，也就是2。接著繼續用相同的方式處理。
第二回合的排序結果為：2、1、4、3、5、7、6、8、9。第三回合的間隔同樣是上回合的一半，由於是1，意味著這是最後一回合。
第三回合的排序結果為：1、2、3、4、5、6、7、8、9。可以注意到，最後一回合就是一般的插入排序法。若再觀察得細一點，會發現這回合只有在插入1、3、6時才會搬移資料，並且都只搬移一項。
三、程式實作
由於筆者將在第四節解說時間複雜度，為方便分析，會額外宣告 roundStepCount 與 allStepCount 的全域變數。它們是用來紀錄元素的比較與搬移次數，前者是該回合的次數，後者是累積次數。另外也宣告 reportRoundEnd 方法，用以在每回合結束時印出次數。
public class ShellSort {
private static int roundStepCount = 0;
private static int allStepCount = 0;
private static void reportRoundEnd() {
System.out.println("回合步驟數: " + roundStepCount);
allStepCount += roundStepCount;
roundStepCount = 0;
}
}
首先準備「尋找小於等於自己的最大資料」的程式。在第二節的示意圖中會發現，對於參與插入排序法的元素，我們需要額外考慮位置範圍。此處用 startIndex 與 endIndex 參數來限制。而 value 的值與下一項元素相比時，要越過一個間隔，此處用 gap 參數來輔助。
private static int lastIndexOfLowerOrEqualData(int[] array, int startIndex, int endIndex, int gap, int value) {
for (int i = endIndex; i >= startIndex; i -= gap) {
roundStepCount++;
if (array[i] <= value) {
return i;
}
}
return startIndex - gap;
}
接著再實作有考慮間隔的插入排序法。我們從參與元素的位置範圍的第二項開始，越過間隔插入到已排序的元素中。
private static void insertionSort(int[] array, int startIndex, int gap) {
for (int currentIndex = startIndex + gap; currentIndex < array.length; currentIndex += gap) {
int currentValue = array[currentIndex];
int newIndex = lastIndexOfLowerOrEqualData(array, startIndex, currentIndex - gap, gap, currentValue) + gap;
for (int i = currentIndex; i > newIndex; i -= gap) {
roundStepCount++;
array[i] = array[i - gap];
}
array[newIndex] = currentValue;
}
}
最後再完成謝耳排序法，關鍵在於如何利用間隔正確地呼叫插入排序法。我們知道第一回合的間隔是元素數量的一半，之後持續減半，直到最後一回合是1。這邊使用 for 迴圈並搭配 gap 變數來控制回合數。
public static void sort(int[] data) {
for (int gap = data.length / 2; gap > 0; gap /= 2) {
// TODO
}
}
接著從第一項元素開始，越過間隔對元素做插入排序法。這邊使用內層 for 迴圈，並搭配 startIndex 變數來指向每次參與元素的起始位置。且 startIndex 變數最多只會指向第一項元素越過一個間隔的前一項。因為若再往後，參與元素便會是先前排序過的組合。
public static void sort(int[] data) {
for (int gap = data.length / 2; gap > 0; gap /= 2) {
for (int startIndex = 0; startIndex < gap; startIndex++) {
insertionSort(data, startIndex, gap);
}
reportRoundEnd();
}
System.out.printf("總步驟數: %d\n", allStepCount);
}
以下為謝耳排序法的完整程式碼
https://gist.github.com/ntub46010/0b4c7e4bb408ce0c80fb7a6ffafbedca
四、時間複雜度（最佳情況）
謝耳排序法的時間複雜度，在推導上比較複雜，因此在範例程式中會印出元素的比較及搬移次數的加總，以下稱「步驟數」。
假設原始資料有16項（以n表示），且已經遞增排序：
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
此時再進行一次遞增排序，印出的內容是：
回合步驟數: 8
回合步驟數: 12
回合步驟數: 14
回合步驟數: 15
總步驟數: 49
回想在第二節用3個回合排序9項資料，那麼8項資料理應也可用3個回合完成。我們得知排序的回合數為「log2n」（小數點捨去），意即此處16項元素需要進行 log216 = 4 個回合的排序。
接著再仔細觀察「8、12、14、15」這個數列，可以注意到每回合的步驟數相當於16（元素數量）減去不同值，且這些值正好是等比數列。
8 = 16 – 8
12 = 16 – 4
14 = 16 – 2
15 = 16 – 1
該等比數列的首項為8（即n/2），末項為1，公比為1/2，經過計算，等比級數為 n - 1。
最後將所有回合的步驟數加總。4個16相當於「回合數 × 元素數量」，等比級數則是「元素數量 - 1」。計算步驟數後得到「log2n × n - ( n - 1)」，故時間複雜度為 O(nlog2n)。
五、時間複雜度（最差情況）
假設原始資料有16項（以n表示），且已經遞減排序：
16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
此時若進行遞增排序，印出的內容是：
回合步驟數: 16接著如同第四節，仔細觀察「16、24、28、30」這個數列，可以注意到每回合的步驟數相當於32（元素數量的兩倍）減去不同值，且這些值正好是等比數列。
回合步驟數: 24
回合步驟數: 28
回合步驟數: 30
總步驟數: 98
16 = 32 - 16該等比數列的首項為16（即2n），末項為2，公比為1/2。經過數學計算，等比級數為 2n - 2。
24 = 32 - 8
28 = 32 - 4
30 = 32 - 2
最後將所有回合的步驟數加總。4個32相當於「回合數 × 元素數量 × 2」，等比級數則是「2 × 元素數量 - 2」。計算步驟數後得到「log2n × 2n - (2n - 2)」，是已排序情況下的2倍，但時間複雜度仍為 O(nlog2n)。
六、不穩定排序
謝耳排序法加入了間隔的概念，由於插入排序法每次參與元素的起始位置並不同，因此相同元素中，較後面的那一個將有機會被插入到更前面的位置。舉例來說，下圖中的原始資料為：2、11、12、3。其中包含兩個「1」，我們以編號區別它們。排序過程如下。
在謝耳排序法的同一回合，當插入排序法的起始位置越後面，即便參與元素包含了很小的元素，往前移動的空間仍受限越大。在上圖中，第一列參與元素的「12」，由於起始位置更前面，因此能移動到第一項。而第二列參與元素的「11」即便是最小值，最多也只能移動到第二項。
由於最後這兩個「1」的相對位置改變了，因此謝耳排序法屬於不穩定排序。
留言
張貼留言