排序算法實(shí)驗(yàn)報(bào)告-展示頁(yè)
2024-08-16 21:18本頁(yè)面
【正文】 序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。 時(shí)效分析： 時(shí)間復(fù)雜度：O（n^2）2. 插入排序—希爾排序（Shell`s Sort）希爾排序是1959 提出來(lái)的，相對(duì)直接排序有較大的改進(jìn)。直接插入排序示例： 如果碰見一個(gè)和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。 即：先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入，直至整個(gè)序列有序?yàn)橹埂Ｎ覀冞@里說(shuō)說(shuō)八大排序就是內(nèi)部排序?；鶖?shù)排序就是這樣，先按低位排序，逐次按高位排序，低位相同的元素其順序再高位也相同時(shí)是不會(huì)改變的。 希爾排序 (4)線性階(O(n))排序 基數(shù)排序，此外還有桶、箱排序。))排序,167。(2)線性對(duì)數(shù)階(O(nlog2n))排序 快速排序、堆排序和歸并排序；一般的選擇都是時(shí)間復(fù)雜度為O(nlog2n)的排序方法。三、 穩(wěn)定性，時(shí)間復(fù)雜度和空間復(fù)雜度分析 2. 八種排序算法的C語(yǔ)言編程實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告八種排序算法實(shí)驗(yàn)報(bào)告一、 實(shí)驗(yàn)內(nèi)容編寫關(guān)于八種排序算法的C語(yǔ)言程序，要求包含直接插入排序、希爾排序、簡(jiǎn)單選擇排序、堆排序、冒泡排序、快速排序、歸并排序和基數(shù)排序。二、 實(shí)驗(yàn)步驟 各種內(nèi)部排序算法的比較：1. 八種排序算法的復(fù)雜度分析（時(shí)間與空間）。3. 八種排序算法的比較，包括比較次數(shù)、移動(dòng)次數(shù)。比較時(shí)間復(fù)雜度函數(shù)的情況：時(shí)間復(fù)雜度函數(shù)O(n)的增長(zhǎng)情況所以對(duì)n較大的排序記錄。時(shí)間復(fù)雜度來(lái)說(shuō)：(1)平方階(O(n2))排序 各類簡(jiǎn)單排序:直接插入、直接選擇和冒泡排序； (3)O(n1+167。是介于0和1之間的常數(shù)。說(shuō)明：當(dāng)原表有序或基本有序時(shí)，直接插入排序和冒泡排序?qū)⒋蟠鬁p少比較次數(shù)和移動(dòng)記錄的次數(shù)，時(shí)間復(fù)雜度可降至O（n）；而快速排序則相反，當(dāng)原表基本有序時(shí)，將蛻化為冒泡排序，時(shí)間復(fù)雜度提高為O（n2）；原表是否有序，對(duì)簡(jiǎn)單選擇排序、堆排序、歸并排序和基數(shù)排序的時(shí)間復(fù)雜度影響不大。穩(wěn)定性：排序算法的穩(wěn)定性:若待排序的序列中，存在多個(gè)具有相同關(guān)鍵字的記錄，經(jīng)過排序， 這些記錄的相對(duì)次序保持不變，則稱該算法是穩(wěn)定的；若經(jīng)排序后，記錄的相對(duì) 次序發(fā)生了改變，則稱該算法是不穩(wěn)定的。穩(wěn)定性的好處：排序算法如果是穩(wěn)定的，那么從一個(gè)鍵上排序，然后再?gòu)牧硪粋€(gè)鍵上排序，第一個(gè)鍵排序的結(jié)果可以為第二個(gè)鍵排序所用。另外，如果排序算法穩(wěn)定，可以避免多余的比較；穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序四、 設(shè)計(jì)細(xì)節(jié)排序有內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。1. 插入排序直接插入排序（Straight lnsertion Sort） 基本思想： 將一個(gè)記錄插入到已排序好的有序表中，從而得到一個(gè)新，記錄數(shù)增1的有序表。要點(diǎn)：設(shè)立哨兵，作為臨時(shí)存儲(chǔ)和判斷數(shù)組邊界之用。所以，相等元素的前后順序沒有改變，從原無(wú)序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的。希爾排序又叫縮小增量排序 基本思想： 先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。僅增量因子為1
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1