基本思想
先取一個小于n的整數d1作為第一個增量，把待排序的全部記錄分成dx個組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插人排序。然后，取第二個增量d2<d1重復上述的分組和排序。直至所取的增量dt=1(dt<dt-x<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。算法實現
希爾排序算法，java實現，代碼如下所示：
public abstract class Sorter { public abstract void sort(int[] array); } public class ShellSorter extends Sorter { @Override public void sort(int[] array) { int d = array.length; do { d /= 2; shellPass(array, d); // 根據逐漸減小的間隔增量，循環調用一趟排序 } while (d > 1); } /** * 希爾一趟排序 * @param d 間隔增量 */ PRivate void shellPass(int[] array, int d) { Integer tmp; for (int i = d; i < array.length; i++) { // 數組下標從0開始，初始i=d表示一趟排序中第二個元素 tmp = array[i]; // array[i]的拷貝 // 如果待處理的無序區第一個元素array[i] < 有序區最大的元素array[i-d] // 需要將有序區比array[i]大的元素向后移動 if (array[i] < array[i - d]) { int j = i - d; while (j >= 0 && tmp < array[j]) { array[j + d] = array[j]; // 將左側有序區中元素比array[i]大的array[j+d]后移 j -= d; } // 如果array[i] >= 左側有序區最大的array[i-d]，或者經過掃描移動后，找到一個比array[i]小的元素 // 將右側無序區第一個元素tmp = array[i]放到正確的位置上 array[j + d] = tmp; } } } }排序過程
希爾排序的過程如下：
首先初始化間隔d為待排序數組的長度，無需排序。減小d，對于每次得到的間隔d，執行多組排序，使得原始數組間隔為d的一個子數組為有序，該數組通過類似直接插入排序的算法來執行排序。直到，d減小為1的時候，整個數組為有序。這里，采用二分的策略來得到間隔d。下面通過例子來說明，執行希爾排序的過程，如下所示：假設待排序數組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數組大小為20。整個排序過程的分組情況，如下所示：
1 | {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49} |
2 | {37,5,34,76,26,9,0,37,55,49, 94,12,68,83,90,37,12,65,76,76} |
3 | {9,0,34,55,26, 37,5,37,76,49, 37,12,65,76,76, 94,12,68,83,90} |
4 | {5,0, 9,12,12, 37,26, 37,34,49, 37,55, 65,68,76, 76,76, 90,83,94} |
5 | {0, 5, 9, 12,12, 26, 34, 37, 37,37, 49, 55, 65, 68,76, 76, 76, 83, 90,94} |
下面說明詳細過程：首先，初始化d = 20。在循環中反復得到間隔d，根據d執行一趟希爾排序。
對于d = 20/2 = 10：根據d = 10來對數組排序，將原始數組分成2塊： {94,12,34,76,26,9,0,37,55,76}與{37,5,68,83,90,37,12,65,76,49}，也就是對如下數組分別進行直接插入排序：{array[0],array[10]} = {94,37}{array[1],array[11]} = {12,5}{array[2],array[12]} = {34,68}{array[3],array[13]} = {76,83}{array[4],array[14]} = {26,90}{array[5],array[15]} = {9,37}{array[6],array[16]} = {0,12}{array[7],array[17]} = {37,65}{array[8],array[18]} = {55,76}{array[9],array[19]} = {76,49}第一趟希爾排序后，各個子數組變為：{37,5,34,76,26,9,0,37,55,49}與{94,12,68,83,90,37,12,65,76,76}，即：array = {37,5,34,76,26,9,0,37,55,49,94,12,68,83,90,37,12,65,76,76}，
對于d = 10/2 = 5：根據d = 5來對數組排序，將第一趟希爾排序后的數組分成4塊 ：{37,5,34,76,26}、{9,0,37,55,49}、{94,12,68,83,90}與{37,12,65,76,76}，也就是對如下數組分別進行直接插入排序：{array[0],array[5],array[10],array[15]} = {37,9,94,37}{array[1],array[6],array[11],array[16]} = {5,0,12,12}{array[2],array[7],array[12],array[17]} = {34,37,68,65}{array[3],array[8],array[13],array[18]} = {76,55,83,76}{array[4],array[9],array[14],array[19]} = {26,49,90,76}第二趟希爾排序后，各個子數組變為：{9,0,34,55,26}、{37,5,37,76,49}、{37,12,65,76,76}與{94,12,68,83,90}，即：array = {9,0,34,55,26,37,5,37,76,49,37,12,65,76,76,94,12,68,83,90}。
對于d = 5/2 = 2：根據d = 2來對數組排序，將第二趟希爾排序后的數組分成10塊： {9,0}、{34,55}、{26,37}、{5,37}、{76,49}、{37,12}、{65,76}、{76,94}、{12,68}與{83,90}，也就是對如下數組分別進行直接插入排序：{array[0],array[2],array[4],array[6],array[8],array[10],array[12],array[14],array[16],array[18]} = {9,34,26,5,76,37,65,76,12,83}{array[1],array[3],array[5],array[7],array[9],array[11],array[13],array[15],array[17],array[19]} = {0,55,37,37,49,12,76,94,68,90}第三趟希爾排序后，各個子數組變為：{5,0}、{9,12}、{12,37}、{26,37}、{34,49}、{37,55}、{65,68}、{76,76}、{76,90}與{83,94}，即：array = ：{5,0,9,12,12,37,26,37,34,49,37,55,65,68,76,76,76,90,83,94}。
對于d = 2/2 = 1：根據d = 1來對數組排序，將第二趟希爾排序后的數組分成20塊：{5}、{0}、{9}、{12}、{12}、{37}、{26}、{37}、{34}、{49}、{37}、{55}、{65}、{68}、{76}、{76}、{76}、{90}、{83}、{94}，也就是對如下數組分別進行直接插入排序：{5,0,9,12,12,37,26,37,34,49,37,55,65,68,76,76,76,90,83,94}第四趟希爾排序以后，數組已經有序：array = {0,5,9,12,12,26,34,37,37,37,49,55,65,68,76,76,76,83,90,94}。因為 d= 1，希爾排序結束。
算法分析
希爾排序是基于插入排序的一種算法， 它的時間復雜度與增量序列的選取有關，例如：
希爾提出了增量序列 h1 ，h2 ，……，ht ，只要h1=1，任何增量序列都是可行的，使用希爾增量排序的時間復雜度為O(n^2)。Hibbard提出了一個增量序列：2^k-1，使用Hibbard增量排序的時間復雜度為O(n^(3/2))。Sedgewick提出了幾種增量序列：9*4i – 9*2i +1 或者是 4i – 3* 2i + 1，最壞運行時間為O(n^(4/3))，對這些增量序列的平均運行時間猜測為O(n^(7/6))。但是現今仍然沒有人能找出希爾排序的精確下界。希爾排序沒有快速排序算法快O(nlogn)，因此中等大小規模表現良好，對規模非常大的數據排序不是最優選擇。但是比O(n^2)復雜度的算法快得多。此外，希爾算法在最壞的情況下和平均情況下執行效率相差不是很多，與此同時快速排序在最壞的情況下執行的效率會非常差。專家們提倡，幾乎任何排序工作在開始時都可以用希爾排序，若在實際使用中證明它不夠快，再改成快速排序這樣更高級的排序算法。本質上講，希爾排序算法是直接插入排序算法的一種改進，減少了其復制的次數，速度要快很多，原因是，當n值很大時數據項每一趟排序需要的個數很少，但數據項的距離很長。當n值減小時每一趟需要和動的數據增多，此時已經接近于它們排序后的最終位置。 正是這兩種情況的結合才使希爾排序效率比插入排序高很多。
時間復雜度希爾排序的效率很大程度上依賴于增量序列的選擇，好的增量序列有如下共同特征：
最后一個增量必須為1。應該盡量避免序列中的值（尤其是相鄰的值）互為倍數的情況。有人通過大量的實驗，給出了較好的結果：當n較大時，比較和移動的次數約在n^1.25到1.6*n^1.25之間。另外，希爾排序的時間性能優于直接插入排序，原因是：
當文件初態基本有序時直接插入排序所需的比較和移動次數均較少。當n值較小時，n和的差別也較小，即直接插入排序的最好時間復雜度O(n)和最壞時間復雜度0()差別不大。在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組內直接插入較快，后來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由于已經按di-1作為距離排過序，使文件較接近于有序狀態，所以新的一趟排序過程也較快。因此，希爾排序在效率上較直接插入排序有較大的改進。
空間復雜度因為希爾排序依賴于增量序列，從而導致排序的趟數不固定，對于不同的增量執行一趟希爾排序，只用到一個輔助變量，所以空間復雜度為O(n)。
排序穩定性由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩定性就會被打亂，通過上述元素76可以看到，希爾排序不穩定。
因此，希爾排序是不穩定的。
新聞熱點
疑難解答
