VR開發(fā)入門教程43：簡單算法之希爾排序

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

　　步驟分析：

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

　　2、首先需要選取關(guān)鍵字,例如關(guān)鍵是3和1(第一步分成三組,第二步分成一組),那么待排數(shù)組分成了以下三個(gè)虛擬組:[6 1]一組、[2 5]二組、[4 9]三組。注意不是臨近的兩個(gè)數(shù)字分組,而是下標(biāo)為3(分成了三組)的倍數(shù)的數(shù)字的分成了一組,就是每隔3個(gè)數(shù)取一個(gè),每隔三個(gè)再取一個(gè),這樣取出來的數(shù)字放到一組,

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

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

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

　　具體過程:

　　[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í)際上就是只有一組啦,隔一取一就全部取出來了

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

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

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

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

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

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

　　如何選取關(guān)鍵字

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

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

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

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

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

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

　　增量的取值規(guī)則：為第一次取總長度的一半,第二次取一半的一半,依次類推直到1為止

　　總的說來希爾對插入排序進(jìn)行了改造

　　原理：為了在插入排序前達(dá)到整個(gè)序列基本有序的狀態(tài) 提高插入排序的效率

　　static void ShellSort(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;

　　}

　　}

　　}

　　}

　　}