亚洲最大看欧美片,亚洲图揄拍自拍另类图片,欧美精品v国产精品v呦,日本在线精品视频免费

  • 站長(zhǎng)資訊網(wǎng)
    最全最豐富的資訊網(wǎng)站

    穩(wěn)定的排序算法有哪些

    穩(wěn)定的排序算法有:1、冒泡排序;2、選擇排序;3、插入排序;4、快速排序;5、歸并排序;6、基數(shù)排序;7、希爾排序(shell);8、堆排序。

    穩(wěn)定的排序算法有哪些

    本教程操作環(huán)境:windows10系統(tǒng)、Dell G3電腦。

    分析一下常見(jiàn)的排序算法的穩(wěn)定性,每個(gè)都給出簡(jiǎn)單的理由。

    穩(wěn)定的排序算法:

    1、冒泡排序

    冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較,交換也發(fā)生在這兩個(gè)元素之間。所以,如果兩個(gè)元素相等,我想你是不會(huì)再無(wú)聊地把他們倆交換一下的。

    如果兩個(gè)相等的元素沒(méi)有相鄰,那么即使通過(guò)前面的兩兩交換把兩個(gè)相鄰起來(lái),這時(shí)候也不會(huì)交換,所以相同元素的前后順序并沒(méi)有改變,所以冒泡排序是一種穩(wěn)定排序算法。

    2、選擇排序

    選擇排序是給每個(gè)位置選擇當(dāng)前元素最小的,比如給第一個(gè)位置選擇最小的,在剩余元素里面給第二個(gè)元素選擇第二小的,依次類推,直到第n-1個(gè)元素,第n個(gè)元素不用選擇了,因?yàn)橹皇O滤粋€(gè)最大的元素了。那么,在一趟選擇,如果當(dāng)前元素比一個(gè)元素小,而該小的元素又出現(xiàn)在一個(gè)和當(dāng)前元素相等的元素后面,那么交換后穩(wěn)定性就被破壞了。

    比較拗口,舉個(gè)例子,序列5 8 5 2 9,我們知道第一遍選擇第1個(gè)元素5會(huì)和2交換,那么原序列中2個(gè)5的相對(duì)前后順序就被破壞了,所以選擇排序不是一個(gè)穩(wěn)定的排序算法。

    3、插入排序

    插入排序是在一個(gè)已經(jīng)有序的小序列的基礎(chǔ)上,一次插入一個(gè)元素。當(dāng)然,剛開始這個(gè)有序的小序列只有1個(gè)元素,就是第一個(gè)元素。比較是從有序序列的末尾開始,也就是想要插入的元素和已經(jīng)有序的最大者開始比起,如果比它大則直接插入在其后面,否則一直往前找直到找到它該插入的位置。

    如果碰見(jiàn)一個(gè)和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。

    所以,相等元素的前后順序沒(méi)有改變,從原無(wú)序序列出去的順序就是排好序后的順序,所以插入排序是穩(wěn)定的。

    4、快速排序

    快速排序有兩個(gè)方向,左邊的i下標(biāo)一直往右走,當(dāng)a[i] <= a[center_index],其中center_index是中樞元素的數(shù)組下標(biāo),一般取為數(shù)組第0個(gè)元素。而右邊的j下標(biāo)一直往左走,當(dāng)a[j]>a[center_index]。

    如果i和j都走不動(dòng)了,i<=j,交換a[i]a[j],重復(fù)上面的過(guò)程,直到i>j。交換a[j]a[center_index],完成一趟快速排序。在中樞元素和a[j]交換的時(shí)候,很有可能把前面的元素的穩(wěn)定性打亂,比如序列為5 3 3 4 3 8 9 10 11,現(xiàn)在中樞元素53(第5個(gè)元素,下標(biāo)從1開始計(jì))交換就會(huì)把元素3的穩(wěn)定性打亂,所以快速排序是一個(gè)不穩(wěn)定的排序算法,不穩(wěn)定發(fā)生在中樞元素和a[j] 交換的時(shí)刻。

    5、歸并排序

    歸并排序是把序列遞歸地分成短序列,遞歸出口是短序列只有1個(gè)元素(認(rèn)為直接有序)或者2個(gè)序列(1次比較和交換),然后把各個(gè)有序的段序列合并成一個(gè)有序的長(zhǎng)序列,不斷合并直到原序列全部排好序。可以發(fā)現(xiàn),在1個(gè)或2個(gè)元素時(shí),1個(gè)元素不會(huì)交換,2個(gè)元素如果大小相等也沒(méi)有人故意交換,這不會(huì)破壞穩(wěn)定性。

    那么,在短的有序序列合并的過(guò)程中,穩(wěn)定是是否受到破壞?

    沒(méi)有,合并過(guò)程中我們可以保證如果兩個(gè)當(dāng)前元素相等時(shí),我們把處在前面的序列的元素保存在結(jié)果序列的前面,這樣就保證了穩(wěn)定性。所以,歸并排序也是穩(wěn)定的排序算法。

    6、基數(shù)排序

    基數(shù)排序是按照低位先排序,然后收集;

    再按照高位排序,然后再收集;

    依次類推,直到最高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的,先按低優(yōu)先級(jí)排序,再按高優(yōu)先級(jí)排序,最后的次序就是高優(yōu)先級(jí)高的在前,高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前?;鶖?shù)排序基于分別排序,分別收集,所以其是穩(wěn)定的排序算法。

    7、希爾排序(shell)

    希爾排序是按照不同步長(zhǎng)對(duì)元素進(jìn)行插入排序,當(dāng)剛開始元素很無(wú)序的時(shí)候,步長(zhǎng)最大,所以插入排序的元素個(gè)數(shù)很少,速度很快。

    當(dāng)元素基本有序了,步長(zhǎng)很小, 插入排序?qū)τ谟行虻男蛄行屎芨?。所以,希爾排序的時(shí)間復(fù)雜度會(huì)比O(n^2)好一些。由于多次插入排序,我們知道一次插入排序是穩(wěn)定的,不會(huì)改變相同元素的相對(duì)順序,但在不同的插入排序過(guò)程中,相同的元素可能在各自的插入排序中移動(dòng),最后其穩(wěn)定性就會(huì)被打亂,所以shell排序是不穩(wěn)定的。

    8、堆排序

    我們知道堆的結(jié)構(gòu)是節(jié)點(diǎn)i的孩子為2 * i2 * i + 1節(jié)點(diǎn),大頂堆要求父節(jié)點(diǎn)大于等于其2個(gè)子節(jié)點(diǎn),小頂堆要求父節(jié)點(diǎn)小于等于其2個(gè)子節(jié)點(diǎn)。在一個(gè)長(zhǎng)為n的序列,堆排序的過(guò)程是從第n / 2開始和其子節(jié)點(diǎn)共3個(gè)值選擇最大(大頂堆)或者最小(小頂堆),這3個(gè)元素之間的選擇當(dāng)然不會(huì)破壞穩(wěn)定性。但當(dāng)為n / 2-1n/2-2,...1這些個(gè)父節(jié)點(diǎn)選擇元素時(shí),就會(huì)破壞穩(wěn)定性。有可能第n/2個(gè)父節(jié)點(diǎn)交換把后面一個(gè)元素交換過(guò)去了,而第n/2-1個(gè)父節(jié)點(diǎn)把后面一個(gè)相同的元素沒(méi)有交換,那么這2個(gè)相同的元素之間的穩(wěn)定性就被破壞了。所以,堆排序不是穩(wěn)定的排序算法。

    贊(0)
    分享到: 更多 (0)
    網(wǎng)站地圖   滬ICP備18035694號(hào)-2    滬公網(wǎng)安備31011702889846號(hào)