日韩 亚洲一区二_久久vs国产综合色大全_国产精品福利在线_欧美在线一级A片免费观看欧美在线_女同性毛片60分钟

您現(xiàn)在所在的位置：首頁(yè) >學(xué)習(xí)資源 > Unity遊戲/VR/AR入門(mén)教材 > VR開(kāi)發(fā)入門(mén)教程43：簡(jiǎn)單算法之希爾排序

VR開(kāi)發(fā)入門(mén)教程43：簡(jiǎn)單算法之希爾排序

來(lái)源：奇酷教育 發(fā)表於：

VR開(kāi)發(fā) VR視頻 VR培訓(xùn)

　　希爾排序

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

　　步驟分析：

　　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]三組。注意不是臨近的兩(liǎng)個(gè)數(shù)字分組,而是下標(biāo)為3(分成了三組)的倍數(shù)的數(shù)字的分成了一組,就是每隔3個(gè)數(shù)取一個(gè),每隔三個(gè)再取一個(gè),這樣取出來(lái)的數(shù)字放到一組,

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

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

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

　　具體過(guò)程:

　　[6 1]6和1交換(huàn)變成[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)行插入排序

　　還記得插入排序怎麼排不?複習(xí)一下

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

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

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

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

　　希爾排序的關(guān)鍵是如何取關(guān)鍵字,因為其它內(nèi)容與插入排序一樣

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

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

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

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

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

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

　　總的說(shuō)來(lái)希爾對(duì)插入排序進(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;

　　}

　　}

　　}

　　}

　　}