希爾排序Shell Sort是基于插入排序的一種改進(jìn),同樣分成兩部分,

第一部分,希爾排序介紹

第二部分,如何選取關(guān)鍵字,選取關(guān)鍵字是希爾排序的關(guān)鍵

第一塊希爾排序介紹

準(zhǔn)備待排數(shù)組[6 2 4 1 5 9]

首先需要選取關(guān)鍵字,例如關(guān)鍵是3和1(第一步分成三組,第二步分成一組),那么待排數(shù)組分成了以下三個(gè)虛擬組:

[6 1]一組

[2 5]二組

[4 9]三組

看仔細(xì)啊,不是臨近的兩個(gè)數(shù)字分組,而是3(分成了三組)的倍數(shù)的數(shù)字分成了一組,

就是每隔3個(gè)數(shù)取一個(gè),每隔三個(gè)再取一個(gè),這樣取出來(lái)的數(shù)字放到一組,

把它們當(dāng)成一組,但不實(shí)際分組,只是當(dāng)成一組來(lái)看,所以上邊的"組"實(shí)際上并不存在,只是為了說(shuō)明分組關(guān)系

對(duì)以上三組分別進(jìn)行插入排序變成下邊這樣

[1 6] [2 5] [4 9]

具體過(guò)程:

[6 1]6和1交換變成[1 6]

[2 5]2與5不動(dòng)還是[2 5]

[4 9]4與9不動(dòng)還是[4 9]

第一趟排序狀態(tài)演示:

待排數(shù)組:[6?2 4?1?5 9]

排后數(shù)組:[1?2 4?6?5 9]

第二趟關(guān)鍵字取的是1,即每隔一個(gè)取一個(gè)組成新數(shù)組,實(shí)際上就是只有一組啦,隔一取一就全部取出來(lái)了嘛

此時(shí)待排數(shù)組為:[1 2 4 6 5 9]

直接對(duì)它進(jìn)行插入排序

還記得插入排序怎么排不?復(fù)習(xí)一下

[1 2 4]都不用動(dòng),過(guò)程省略,到5的時(shí)候,將5取出,在前邊的有序數(shù)組里找到適合它的位置插入,就是4后邊,6前邊

后邊的也不用改,所以排序完畢

順序輸出結(jié)果:[1 2 4 5 6 9]

第二塊希爾排序的關(guān)鍵是如何取關(guān)鍵字,因?yàn)槠渌鼉?nèi)容與插入排序一樣

那么如何選取關(guān)鍵字呢?就是分成三組,一組,這個(gè)分組的依據(jù)是什么呢?為什么不是二組,六組或者其它組嘞?

好的增量序列的共同特征:

① 最后一個(gè)增量必須為1

② 應(yīng)該盡量避免序列中的值(尤其是相鄰的值)互為倍數(shù)的情況

參見(jiàn)?http://baike.baidu.com/view/2217047.htm

這么關(guān)鍵的問(wèn)題竟然沒(méi)有一個(gè)公式,只給出了兩個(gè)判定標(biāo)準(zhǔn)

好吧,一般10個(gè)待排數(shù)字的話,關(guān)鍵依次選取5 3 1即可,其它的情況只能自己判斷了,然后看是否符合上述兩條"好"的標(biāo)準(zhǔn)

就是說(shuō),這個(gè)關(guān)鍵的選擇是沒(méi)有規(guī)定的,怎么選都可以,僅一條,關(guān)鍵字要越來(lái)越小,直到1為止

后補(bǔ):

增量的取值規(guī)則為第一次取總長(zhǎng)度的一半,第二次取一半的一半,依次累推直到1為止!

以下C#代碼實(shí)現(xiàn)供參考

static void shell_sort(int[] unsorted, int len){int group, i, j, temp;for (group = len / 2; group > 0; group /= 2){for (i = group; i < len; i++){for (j = i - group; j >= 0; j -= group){if (unsorted[j] > unsorted[j + group]){temp = unsorted[j];unsorted[j] = unsorted[j + group];unsorted[j + group] = temp;}}}}}static void Main(string[] args){int[] x = { 6, 2, 4, 1, 5, 9 };shell_sort(x, x.Length);foreach (var item in x){Console.WriteLine(item);}Console.ReadLine();}

總結(jié)

以上是生活随笔為你收集整理的希尔排序-Java二的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。