## **希爾排序（插入排序的改良版）** 在希爾排序出現之前，計算機界普遍存在“排序算法不可能突破O(n2)”的觀點。希爾排序是第一個突破O(n2)的排序算法，它是簡單插入排序的改進版。希爾排序的提出，主要基于以下兩點： 1. 插入排序算法在數組基本有序的情況下，可以近似達到O(n)復雜度，效率極高。 2. 但插入排序每次只能將數據移動一位，在數組較大且基本無序的情況下性能會迅速惡化。 ## **算法描述** 先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，具體算法描述： * 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1； * 按增量序列個數k，對序列進行 k 趟排序； * 每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。 ## **希爾排序的增量** 希爾排序的增量數列可以任取，需要的唯一條件是最后一個一定為1（因為要保證按1有序）。但是，不同的數列選取會對算法的性能造成極大的影響。上面的代碼演示了兩種增量。 切記：增量序列中每兩個元素最好不要出現1以外的公因子！（很顯然，按4有序的數列再去按2排序意義并不大）。 下面是一些常見的增量序列。 \- 第一種增量是最初Donald Shell提出的增量，即折半降低直到1。據研究，使用希爾增量，其時間復雜度還是O(n2)。 第二種增量Hibbard：{1, 3, ..., 2k-1}。該增量序列的時間復雜度大約是O(n1.5)。 第三種增量Sedgewick增量：(1, 5, 19, 41, 109,...)，其生成序列或者是9*4i**\- 9*2i + 1或者是4i - 3\*2i + 1。 ## **穩定性** 我們都知道插入排序是穩定算法。但是，Shell排序是一個多次插入的過程。在一次插入中我們能確保不移動相同元素的順序，但在多次的插入中，相同元素完全有可能在不同的插入輪次被移動，最后穩定性被破壞，因此，Shell排序不是一個穩定的算法。 ## **適用場景** Shell排序雖然快，但是畢竟是插入排序，其數量級并沒有后起之秀--快速排序O(n㏒n)快。在大量數據面前，Shell排序不是一個好的算法。但是，中小型規模的數據完全可以使用它。 ## **JAVA代碼實現** Donald Shell增量 ``` public static void shellSort(int[] arr){ int temp; for (int delta = arr.length/2; delta>=1; delta/=2){ //對每個增量進行一次排序 for (int i=delta; i<arr.length; i++){ for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ //注意每個地方增量和差值都是delta temp = arr[j-delta]; arr[j-delta] = arr[j]; arr[j] = temp; } }//loop i }//loop delta } ``` O(n3/2) by Knuth ``` public static void shellSort2(int[] arr){ int delta = 1; while (delta < arr.length/3){//generate delta delta=delta*3+1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ... } int temp; for (; delta>=1; delta/=3){ for (int i=delta; i<arr.length; i++){ for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ temp = arr[j-delta]; arr[j-delta] = arr[j]; arr[j] = temp; } }//loop i }//loop delta } ```