希爾排序的基本思想

????希爾排序是插入排序的一種，又稱“縮小增量排序”，希爾排序是直接插入排序算法的一種更高效的改進版本，排序相關(guān)文章推薦:C語言中的排序算法。

希爾排序的基本思想

????設(shè)等待排序等元素序列有n個元素，首先取一個整數(shù)increment（小于n）作為間隔將全部元素分為n/increment個子序列，所有距離為increment的元素放在同一個子序列中，在每一個子序列中分別實行直接插入排序，然后縮小間隔increment，重復(fù)上述子序列劃分和排序工作，直到最后取increment=1，將所有元素放在同一個子序列中排序為止，該方法實質(zhì)上是一種分組插入方法.

關(guān)于增量（increment）的取值

????希爾排序的復(fù)雜度和增量序列是相關(guān)的，一般的初次取序列長度的一半為增量，以后每次減半，直到增量為1，希爾排序中對于增量序列的選擇十分重要，直接影響到希爾排序的性能，一些經(jīng)過優(yōu)化的增量序列如Hibbard經(jīng)過復(fù)雜證明可使得最壞時間復(fù)雜度為O(n3/2)?。

????{1,2,4,8,...}這種序列并不是很好的增量序列，使用這個增量序列的時間復(fù)雜度（最壞情形）是O(n^2)。

??? Hibbard提出了另一個增量序列{1,3,7，...,2^k-1}，這種序列的時間復(fù)雜度(最壞情形)為O(n^1.5)。

??? Sedgewick提出了幾種增量序列，其最壞情形運行時間為O（n^1.3）,其中最好的一個序列是{1,5,19,41,109,...}。?

代碼實現(xiàn)

?

/* 希爾排序*/int num[5] = {3, 7, 1, 8, 5};int cur;int i, j;int length = sizeof(num)/sizeof(num[0]);????int?incre;????incre?=?length?/?2;while (incre >= 1)    {for (i = incre; i < length; i++)        {            cur = num[i];    //待排序元素for (j = i - incre; j >= 0 && num[j] > cur; j = j - incre)            {                num[j + incre] = num[j];    //元素向后移動            }            num[j + incre] = cur;    //插入待排序元素        }        incre = incre / 2;    //增量減半    }

?

??? while里面的代碼其實和插入排序的代碼沒多大區(qū)別，就是在兩個for循環(huán)外面套了一個while再修改了一下內(nèi)部的for循環(huán)，可以對照看一下下面列出來的插入排序的for循環(huán)。

?

for (i = 1; i < length; i++)    {        cur = num[i];    //待排序元素for (j = i - 1; j >= 0 && num[j] > cur; j--)        {            num[j + 1] = num[j];        }        num[j + 1] = cur;    }

?

排序過程

????以5，7，8，3，1，2，4，6為例。

????下面有顏色的是邏輯上的分組，并沒有實際地進行分組操作，在數(shù)組中的位置還是原來的樣子，只是將它們看成這么幾個分組（邏輯上分組）。

????每個分組進行插入排序后，各個分組就變成了有序的了（整體不一定有序）。

????此時，整個數(shù)組變的部分有序了（有序程度可能不是很高）。

????然后縮小增量為上個增量的一半:2，繼續(xù)劃分分組，此時，每個分組元素個數(shù)多了，但是，數(shù)組變的部分有序了，插入排序效率同樣不高。

????同理對每個分組進行排序（插入排序），使其每個分組各自有序。

????最后設(shè)置增量為上一個增量的一半：1，則整個數(shù)組被分為一組，此時，整個數(shù)組已經(jīng)接近有序了，插入排序效率高。

????同理，對這僅有的一組數(shù)據(jù)進行排序，排序完成?！　?/p>