排序算法實(shí)驗(yàn)報告-預(yù)覽頁
【正文】 排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。要點(diǎn)：設(shè)立哨兵，作為臨時存儲和判斷數(shù)組邊界之用。希爾排序又叫縮小增量排序 基本思想： 先將整個待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進(jìn)行依次直接插入排序。n為要排序數(shù)的個數(shù)即：先將要排序的一組記錄按某個增量d（n/2,n為要排序數(shù)的個數(shù)）分成若干組子序列，然后再用一個較小的增量（d/2）對它進(jìn)行分組，在每組中再進(jìn)行直接插入排序。增量因子序列可以有各種取法，有取奇數(shù)的，也有取質(zhì)數(shù)的，但需要注意：增量因子中除1 外沒有公因子，且最后一個增量因子必須為1。4. 選擇排序—堆排序（Heap Sort）堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進(jìn)。如：（a）大頂堆序列：（96, 83,27,38,11,09)依此類推，直到只有兩個節(jié)點(diǎn)的堆，并對它們作交換，最后得到有n個節(jié)點(diǎn)的有序序列。調(diào)整小頂堆的方法：1）設(shè)有m 個元素的堆，輸出堆頂元素后，剩下m1 個元素。則重復(fù)方法 （2）.5）繼續(xù)對不滿足堆性質(zhì)的子樹進(jìn)行上述交換操作，直到葉子結(jié)點(diǎn)，堆被建成。1）n 個結(jié)點(diǎn)的完全二叉樹，則最后一個結(jié)點(diǎn)是第個結(jié)點(diǎn)的子樹。所以堆排序有兩個函數(shù)組成。所以，在建好堆后，排序過程中的篩選次數(shù)不超過下式：冒泡排序的示例：3）此時基準(zhǔn)元素在其排好序后的正確位置4）然后分別對這兩部分記錄用同樣的方法繼續(xù)進(jìn)行排序，直到整個序列有序?？焖倥判蚴且粋€不穩(wěn)定的排序方法。所以對n 個元素的待排序列，每個元素可看成1 個有序子表。有時候有些屬性是有優(yōu)先級順序的，先按低優(yōu)先級排序，再按高優(yōu)先級排序?；撕荛L時間終于把排序的基礎(chǔ)學(xué)了一下，這段時間學(xué)了很多東西，總結(jié)一下：學(xué)的排序算法有：插入排序，合并排序，冒泡排序，選擇排序，希爾排序，堆排序，快速排序，基數(shù)排序。 ，所謂排序穩(wěn)定就是指：如果兩個數(shù)相同，對他們進(jìn)行的排序結(jié)果為他們的相對順序不變。不穩(wěn)定呢就是他們的順序不應(yīng)和開始順序一致。他的名字很棒，快速嘛。但是有一個軟肋就是如果已經(jīng)是排好的情況下時間復(fù)雜度就是n*n,不過在加入隨機(jī)的情況下這種情況也得以好轉(zhuǎn)，而且他可以做任意的比較，只要你能給出兩個元素的大小關(guān)系就可以了。因?yàn)椴挥萌颗拧?shù)據(jù)的移動和交換都很少。還有一點(diǎn)就是加上哨兵之后他可以提前退出。他的好處就是每次只選擇確定的元素，不會對很多數(shù)據(jù)進(jìn)行交換。而其他兩個排序就算已經(jīng)排好了，他也要做全部的掃描。他的思想是分治，先分成小的部分，排好部分之后合并，因?yàn)槲覀兞硗馍暾埖目臻g，在合并的時候效率是0(n)的。但是因?yàn)樗欠窃嘏判颍噪m然他很快，但是貌似他的人氣沒有快速排序高?？墒撬乃枷敫杏X比快速難掌握一些。 ：n*log(n)的時間復(fù)雜度(這里是錯誤的，應(yīng)該是n^lamda(1 lamda 2), lamda和每次步長選擇有關(guān)。分成nLen/2個組，然后每組排序。他的缺點(diǎn)就是兩個數(shù)可能比較多次，因?yàn)閮蓚€數(shù)據(jù)會多次分不過他們不會出現(xiàn)數(shù)據(jù)的交換。每次都確定了一個數(shù)的位置，所以理論上說不會出現(xiàn)兩個數(shù)比較兩次的情況，也是在最后在交換數(shù)據(jù)，說以數(shù)據(jù)交換上也很少。還有他很容易掌握和實(shí)現(xiàn)。只有能保證每個關(guān)鍵字在n的時間復(fù)雜度完成，那么整個排序就是一個d*n的時間復(fù)雜度。所以這些排序的算法都是很好的，他確實(shí)給了我們思想上的幫助。呵呵，這樣就知道在排好的數(shù)據(jù)里面，不用再排序了，而是直接調(diào)用一下插入就可以了。 堆排序：可以用它來實(shí)現(xiàn)優(yōu)先隊(duì)列，而且他的思想應(yīng)該給我加了很多內(nèi)力。
法律信息相關(guān)推薦
鄂ICP備17016276號-1