排序算法實(shí)驗(yàn)報(bào)告-資料下載頁(yè)
2025-08-01 21:18本頁(yè)面
【正文】 個(gè)數(shù)據(jù)在末尾后排序，冒泡只要一次就能搞定，而選擇和插入都必須要n*n的復(fù)雜度才能搞定。 ：n*log(n)的時(shí)間復(fù)雜度， 穩(wěn)定排序，非原地排序。他的思想是分治，先分成小的部分，排好部分之后合并，因?yàn)槲覀兞硗馍暾?qǐng)的空間，在合并的時(shí)候效率是0(n)的。速度很快。貌似他的上限是n*log(n)，所以如果說(shuō)是比較的次數(shù)的話(huà)，他比快速排序要少一些。對(duì)任意的數(shù)組都能有效地在n*log(n)排好序。但是因?yàn)樗欠窃嘏判?，所以雖然他很快，但是貌似他的人氣沒(méi)有快速排序高。 ：n*log(n)的時(shí)間復(fù)雜度， 非穩(wěn)定排序，原地排序。他的思想是利用的堆這種數(shù)據(jù)結(jié)構(gòu)，堆可以看成一個(gè)完全二叉樹(shù)，所以在排序中比較的次數(shù)可以做到很少。加上他也是原地排序，不需要申請(qǐng)額外的空間，效率也不錯(cuò)?？墒撬乃枷敫杏X(jué)比快速難掌握一些。還有就是在已經(jīng)排好序的基礎(chǔ)上添加一個(gè)數(shù)據(jù)再排序，他的交換次數(shù)和比較次數(shù)一點(diǎn)都不會(huì)減少。雖然堆排序在使用的中沒(méi)有快速排序廣泛，但是他的數(shù)據(jù)結(jié)構(gòu)和思想真的很不錯(cuò)，而且用它來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列，效率沒(méi)得說(shuō)。堆，還是要好好學(xué)習(xí)掌握的。 ：n*log(n)的時(shí)間復(fù)雜度(這里是錯(cuò)誤的，應(yīng)該是n^lamda(1 lamda 2), lamda和每次步長(zhǎng)選擇有關(guān)。)， 非穩(wěn)定排序，原地排序。主要思想是分治，不過(guò)他的分治和合并排序的分治不一樣，他是按步長(zhǎng)來(lái)分組的，而不是想合并那樣左一半右一半。開(kāi)始步長(zhǎng)為整個(gè)的長(zhǎng)度的一半。分成nLen/2個(gè)組，然后每組排序。接個(gè)步長(zhǎng)減為原來(lái)的一半在分組排序，直到步長(zhǎng)為1，排序之后希爾排序就完成了。這個(gè)思路很好，據(jù)說(shuō)是插入排序的升級(jí)版，所以在實(shí)現(xiàn)每組排序的時(shí)候我故意用了插入排序。我覺(jué)得他是一個(gè)特別好的排序方法了。他的缺點(diǎn)就是兩個(gè)數(shù)可能比較多次，因?yàn)閮蓚€(gè)數(shù)據(jù)會(huì)多次分不過(guò)他們不會(huì)出現(xiàn)數(shù)據(jù)的交換。效率也是很高的。 ，堆排序，合并排序，希爾排序的比較，他們的時(shí)間復(fù)雜的都是n*log(n)，我認(rèn)為在使用上快速排序最廣泛，他原地排序，雖然不穩(wěn)定，可是很多情況下排序根本就不在意他是否穩(wěn)定。他的比較次數(shù)是比較小的，因?yàn)樗褦?shù)據(jù)分成了大和小的兩部分。每次都確定了一個(gè)數(shù)的位置，所以理論上說(shuō)不會(huì)出現(xiàn)兩個(gè)數(shù)比較兩次的情況，也是在最后在交換數(shù)據(jù)，說(shuō)以數(shù)據(jù)交換上也很少。合并排序和堆排序也有這些優(yōu)點(diǎn)，但是合并排序要申請(qǐng)額外的空間。堆排序堆已經(jīng)排好的數(shù)據(jù)交換上比快速多。所以目前快速排序用的要廣泛的多。還有他很容易掌握和實(shí)現(xiàn)。 ：n的時(shí)間復(fù)雜度，穩(wěn)定排序，非原地排序。他的思想是數(shù)據(jù)比較集中在一個(gè)范圍，例如都是4位數(shù)，都是5位數(shù)，或數(shù)據(jù)有多個(gè)關(guān)鍵字，我們先從各位開(kāi)始排，然后排十位，依次排到最高位，因?yàn)槲覀兛梢杂靡粋€(gè)n的方法排一位，所以總的方法為d*n的復(fù)雜度。關(guān)鍵字也一樣，我們先排第3個(gè)關(guān)鍵字，在排第3個(gè)關(guān)鍵字，最后排第一個(gè)關(guān)鍵字。只有能保證每個(gè)關(guān)鍵字在n的時(shí)間復(fù)雜度完成，那么整個(gè)排序就是一個(gè)d*n的時(shí)間復(fù)雜度。所以總的速度是很快的。不過(guò)有一點(diǎn)就是要確保關(guān)鍵字能在n的時(shí)間復(fù)雜度完成。 ：黑格爾說(shuō)過(guò)：存在即合理。所以這些排序的算法都是很好的，他確實(shí)給了我們思想上的幫助。感謝前人把精華留給了我們。我得到的收獲很大，總結(jié)一下各自排序的收獲： 冒泡：好實(shí)現(xiàn)，速度不慢，使用于輕量級(jí)的數(shù)據(jù)排序。 插入排序：也使用于小數(shù)據(jù)的排序，但是我從他的思想中學(xué)到怎么插入一個(gè)數(shù)據(jù)。呵呵，這樣就知道在排好的數(shù)據(jù)里面，不用再排序了，而是直接調(diào)用一下插入就可以了。 選擇排序：我學(xué)會(huì)了怎么去獲得最大值，最小值等方法。只要選擇一下，不就可以了。 合并排序：我學(xué)會(huì)分而治之的方法，而且在合并兩個(gè)數(shù)組的時(shí)候很適用。 堆排序：可以用它來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列，而且他的思想應(yīng)該給我加了很多內(nèi)力。 快速排序：本來(lái)就用的最多的排序，對(duì)我的幫助大的都不知道怎么說(shuō)好。 希爾排序：也是分治，讓我看到了分治的不同，原來(lái)還有這種思想的存在。 基數(shù)排序：特殊情況特殊處理
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1