觀察一下”插入排序“：其實(shí)不難發(fā)現(xiàn)她有個(gè)缺點(diǎn)：

　　如果當(dāng)數(shù)據(jù)是”5, 4, 3, 2, 1“的時(shí)候，此時(shí)我們將“無(wú)序塊”中的記錄插入到“有序塊”時(shí)，估計(jì)俺們要崩盤，每次插入都要移動(dòng)位置，此時(shí)插入排序的效率可想而知。  

　　shell根據(jù)這個(gè)弱點(diǎn)進(jìn)行了算法改進(jìn)，融入了一種叫做“縮小增量排序法”的思想，其實(shí)也蠻簡(jiǎn)單的，不過(guò)有點(diǎn)注意的就是：

增量不是亂取，而是有規(guī)律可循的。

希爾排序時(shí)效分析很難，關(guān)鍵碼的比較次數(shù)與記錄移動(dòng)次數(shù)依賴于增量因子序列d的選取，特定情況下可以準(zhǔn)確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動(dòng)次數(shù)。目前還沒(méi)有人給出選取最好的增量因子序列的方法。增量因子序列可以有各種取法，有取奇數(shù)的，也有取質(zhì)數(shù)的，但需要注意：增量因子中除1 外沒(méi)有公因子，且最后一個(gè)增量因子必須為1。希爾排序方法是一個(gè)不穩(wěn)定的排序方法。

首先要明確一下增量的取法(這里圖片是copy別人博客的，增量是奇數(shù)，我下面的編程用的是偶數(shù))：

      第一次增量的取法為： d=count/2;

      第二次增量的取法為:  d=(count/2)/2;

      最后一直到: d=1; 

好，注意看圖了，第一趟的增量d1=5, 將10個(gè)待排記錄分為5個(gè)子序列，分別進(jìn)行直接插入排序，結(jié)果為(13, 27, 49, 55, 04, 49, 38, 65, 97, 76)

第二趟的增量d2=3, 將10個(gè)待排記錄分為3個(gè)子序列，分別進(jìn)行直接插入排序，結(jié)果為(13, 04, 49, 38, 27, 49, 55, 65, 97, 76)

第三趟的增量d3=1, 對(duì)整個(gè)序列進(jìn)行直接插入排序，最后結(jié)果為(04, 13, 27, 38, 49, 49, 55, 65, 76, 97)

重點(diǎn)來(lái)了。當(dāng)增量減小到1時(shí)，此時(shí)序列已基本有序，希爾排序的最后一趟就是接近最好情況的直接插入排序?？蓪⑶懊娓魈说?宏觀"調(diào)整看成是最后一趟的預(yù)處理，比只做一次直接插入排序效率更高。

本人是學(xué)python的，今天用python實(shí)現(xiàn)了希爾排序。

def ShellInsetSort(array, len_array, dk): # 直接插入排序
 for i in range(dk, len_array): # 從下標(biāo)為dk的數(shù)進(jìn)行插入排序
 position = i
 current_val = array[position] # 要插入的數(shù)

 index = i
 j = int(index / dk) # index與dk的商
 index = index - j * dk

 # while True: # 找到第一個(gè)的下標(biāo)，在增量為dk中，第一個(gè)的下標(biāo)index必然 0<=index<dk
 # index = index - dk
 # if 0<=index and index <dk:
 # break


 # position>index,要插入的數(shù)的下標(biāo)必須得大于第一個(gè)下標(biāo)
 while position > index and current_val < array[position-dk]:
 array[position] = array[position-dk] # 往后移動(dòng)
 position = position-dk
 else:
 array[position] = current_val



def ShellSort(array, len_array): # 希爾排序
 dk = int(len_array/2) # 增量
 while(dk >= 1):
 ShellInsetSort(array, len_array, dk)
 print(">>:",array)
 dk = int(dk/2)

if __name__ == "__main__":
 array = [49, 38, 65, 97, 76, 13, 27, 49, 55, 4]
 print(">:", array)
 ShellSort(array, len(array))

輸出:

>: [49, 38, 65, 97, 76, 13, 27, 49, 55, 4]
>>: [13, 27, 49, 55, 4, 49, 38, 65, 97, 76]
>>: [4, 27, 13, 49, 38, 55, 49, 65, 97, 76]
>>: [4, 13, 27, 38, 49, 49, 55, 65, 76, 97]

首先你得先會(huì)插入排序，不會(huì)你必然看不懂。 

插入排序，即是對(duì)上圖三個(gè)黃色框中的數(shù)進(jìn)行插入排序。舉個(gè)例子：13，55，38，76

直接看55，55<13, 不用移動(dòng)。接著看38，38<55，那么55后移，數(shù)據(jù)變?yōu)閇13，55，55，76]，接著比較13<38, 那么38替換55，變成[13，38，55，76]。其它同理，略。

這里有個(gè)問(wèn)題，比如第二個(gè)黃色框[27，4，65]，4<27, 那27往后移，接著4就替換第一個(gè)，數(shù)據(jù)變成[4，27，65]，但是計(jì)算機(jī)怎么知道4就是在第一個(gè)啊??

我的做法是，先找出[27，4，65]第一個(gè)數(shù)的下標(biāo)，在這個(gè)例子中27的下標(biāo)為1。當(dāng)要插入的數(shù)的下標(biāo)大于第一個(gè)下標(biāo)1時(shí)，才可以往后移，前一個(gè)數(shù)不可以往后移有兩種情況，一種是前面有數(shù)據(jù)，且小于要插入的數(shù)，那你只能插在它后面。另一種，很重要，當(dāng)要插入數(shù)比前面所有數(shù)都小時(shí)，那插入數(shù)肯定是放在第一個(gè)，此時(shí)要插入數(shù)的下標(biāo)＝第一個(gè)數(shù)的下標(biāo)。(這段話，感覺(jué)初學(xué)者應(yīng)該不大懂……)

為了找到第一個(gè)數(shù)的下標(biāo)，最開始想的是用循環(huán)，一直到最前面:

while True: # 找到第一個(gè)的下標(biāo)，在增量為dk中，第一個(gè)的下標(biāo)index必然 0<=index<dk
 index = index - dk
 if 0<=index and index <dk:
 break

在Debug時(shí)，發(fā)現(xiàn)用循環(huán)太浪費(fèi)時(shí)間了，特別是當(dāng)增量d=1時(shí)，直接插入排序?yàn)榱瞬迦肓斜碜詈笠粋€(gè)數(shù)，得循環(huán)減1，直到第一個(gè)數(shù)的下標(biāo)，后來(lái)我學(xué)聰明了，用下面的方法:

j = int(index / dk) # index與dk的商
index = index - j * dk

時(shí)間復(fù)雜度:

希爾排序的時(shí)間復(fù)雜度是所取增量序列的函數(shù)，尚難準(zhǔn)確分析。有文獻(xiàn)指出，當(dāng)增量序列為d[k]=2^(t-k+1)時(shí)，希爾排序的時(shí)間復(fù)雜度為O(n^1.5), 其中t為排序趟數(shù)。

穩(wěn)定性: 不穩(wěn)定

希爾排序效果: 

參考資料: 編程是我自己實(shí)現(xiàn)的。建議Debug看看運(yùn)行過(guò)程

c++中八大排序算法

視覺(jué)直觀感受若干常用排序算法

C#七大經(jīng)典排序算法系列（下）

1.非系統(tǒng)的學(xué)習(xí)也是在浪費(fèi)時(shí)間 2.做一個(gè)會(huì)欣賞美，懂藝術(shù)，會(huì)藝術(shù)的技術(shù)人

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論