從排序開始（二） 希爾排序

 希爾排序，是對直接插入排序的改進版本，又稱增量縮小排序，實質上是一種分組插入排序。    基本思想是 先取第一個增量step，以該序列內所有下標相差 step 的元素作為一組，如 array[0], array[0 + step], array[0 + step*2].....作為一組，array[1], array[1 + step], array[1 + step*2]....作為一組，然後對這些分組分別進行直接插入排序，然後減小增量，重復進行上面操作，到最後 step = 1，這時序列已基本有序，對數組再次進行直接插入排序，這種情況下的直接插入排序復雜度為 O(n)，而且保證了最後的結果是有序數列。     希爾排序的復雜度比較復雜，主要跟步長的選擇有關，大概是 O(n logn^2)，一般認為就是介於 O(n^2) 和 O(n logn) 之間。最好步長比較復雜，一般第一次取序列的一半，以後每次減半，直到步長為1。     對於希爾排序為什麼明顯優於直接插入排序，讓我們看看維基：“希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然後算法再取越來越小的步長進行排序，算法的最後一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了（此時插入排序較快）。”“可能希爾排序最重要的地方在於當用較小步長排序後，以前用的較大步長仍然是有序的。比如，如果一個數列以步長5進行了排序然後再以步長3進行排序，那麼該數列不僅是以步長3有序，而且是以步長5有序。如果不是這樣，那麼算法在迭代過程中會打亂以前的順序，那就不會以如此短的時間完成排序了。”   復雜度： 最差時間復雜度：根據步長串行的不同而不同。 已知最好的 O(n logn^2) 最優時間復雜度：O(n) 平均時間復雜度：根據步長串行的不同而不同。 最差空間復雜度：O(n)   穩定性：不穩定   實現：  

void shellSort(int data[], int n)  
{  
    int i,j,step;  
    for(step = n/2;step > 0;step /= 2) //步長，每次取一半  
    {  
        for(i = step;i < n; ++i)//從step 開始，每一個元素插入到自己組內  
        {  
            int key = data[i];  
            for(j = i - step;j >= 0 && data[j] > key;j -= step) //找到元素在自己組內的對應位置  
                data[j + step] = data[j];