排序算法比較

《排序算法比較》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、排序算法比較一、課程設(shè)計目的學(xué)習(xí)和鞏固數(shù)據(jù)結(jié)構(gòu)的基本知識。體會在程序設(shè)計中數(shù)據(jù)的重要作用，學(xué)會在程序設(shè)計中運用數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識解決問題。將課本上的理論知識和實際有機(jī)的結(jié)合起來，鍛煉學(xué)生的分析解決實際問題的能力。提高學(xué)生適應(yīng)實際，實踐編程的能力。具體來說，掌握各種排序的基本思想﹑掌握各種排序方法的算法實現(xiàn)﹑掌握各種排序方法的優(yōu)劣分析及花費的時間的計算。二、設(shè)計內(nèi)容和要求利用隨機(jī)函數(shù)產(chǎn)生30000個隨機(jī)整數(shù)，利用插入排序、起泡排序、選擇排序、快速排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計每一種排序上機(jī)所花費的時間。三、工程進(jìn)度及個人任務(wù)（1）工程進(jìn)度：2014.1.1

2、—1.3選題，編寫種排序函數(shù)。2014.1.6—1.9為了不使每次排序都要重新生成帶排序的數(shù)，查找資料編寫如何使程序?qū)崿F(xiàn)將生成的數(shù)都保存到.txt文件中，以后排序后的數(shù)也都保存到.txt文件中。2014.1.10—1.11組合程序，并調(diào)試。2014.1.12完成設(shè)計報告。（2）個人任務(wù):謝奇恩-完成各種排序函數(shù)的編寫及最后的課程報告；韓海真（組長）—實現(xiàn)程序整合優(yōu)化及調(diào)試。四、數(shù)據(jù)定義用順序表作為文件的存儲結(jié)構(gòu)，并且按關(guān)鍵字遞增排序其存儲類型說明如下：#defineMAX60000//記錄數(shù)組的最大值typedefintdatatype;//定義關(guān)鍵字類型typedefs

3、truct{intkey;//記錄的關(guān)鍵字域datatypeother;//記錄的其它字域}rectype;16rectyper[MAX],*s;//將生產(chǎn)的30000個隨機(jī)數(shù)放到r[MAX]數(shù)組存放原始數(shù)據(jù)，*s存放排//序后的數(shù)據(jù)數(shù)據(jù)輸入輸出：由隨機(jī)函數(shù)生產(chǎn)30000個隨機(jī)數(shù)，分別用直接插入排序；直接選擇排序；起泡排序；希爾排序；快速排序；堆排序這些排序方法進(jìn)行排序，輸出每種排序的實際運行時間，將排好的數(shù)存放在.txt文檔中。五、各種排序的基本原理及時間復(fù)雜度分析1、直接插入排序（Insert_Sort）（1）基本原理：假設(shè)待排序的n個記錄{R0，R1，…，Rn}順序

4、存放在數(shù)組中，直接插入法在插入記錄Ri(i=1，2，…，n-1)時，記錄被劃分為兩個區(qū)間[R0,Ri-1]和[Ri+1,Rn-1],其中，前一個子區(qū)間已經(jīng)排好序，后一個子區(qū)間是當(dāng)前未排序的部分，將關(guān)鍵碼Ki與Ki-1Ki-2，…，K0依次比較，找出應(yīng)該插入的位置，將記錄Ri插，然后將剩下的i-1個元素按關(guān)鍵詞大小依次插入該有序序列，沒插入一個元素后依然保持該序列有序，經(jīng)過i-1趟排序后即成為有序序列。每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。（2）時間復(fù)雜度分析：直接插入排序算法必須進(jìn)行n-1趟。最好情況下，

5、即初始序列有序，執(zhí)行n-1趟，但每一趟只比較一次，移動元素兩次，總的比較次數(shù)是(n-1)，移動元素次數(shù)是2(n-1)。因此最好情況下的時間復(fù)雜度就是O(n)。最壞情況(非遞增)下，最多比較i次，因此需要的比較次數(shù)是：所以，時間復(fù)雜度為O(n2)。2、直接選擇排序（Select_Sort）（1）基本原理：待排序的一組數(shù)據(jù)元素中，選出最小的一個數(shù)據(jù)元素與第一個位置的數(shù)據(jù)元素交換；然后在剩下的數(shù)據(jù)元素當(dāng)中再找最小的與第二個位置的數(shù)據(jù)元素交換，循環(huán)到只剩下最后一個數(shù)據(jù)元素為止，依次類推直到所有記錄。第一趟第n個記錄中找出關(guān)鍵碼最小的記錄與第n個記錄交換；第二趟，從第二個記錄開始的

6、，2-1個記錄中再選出關(guān)鍵碼最小的記錄與第二個記錄交換；如此，第i趟，則從第i個記錄開始的n-i+l個記錄中選出關(guān)鍵碼最小的記錄與第i個記錄交換，直到所有記錄排好序。（2）時間復(fù)雜度分析：該算法運行時間與元素的初始排列無關(guān)。不論初始排列如何，該算法都必須執(zhí)行n-1趟，每趟執(zhí)行n-i-1次關(guān)鍵字的比較，這樣總的比較次數(shù)為：所以，簡單選擇排序的最好、最壞和平均情況的時間復(fù)雜度都為O(n2)。3、冒泡排序（bubble_sort）16（1）基本原理：在每一趟冒泡排序中，依次比較相鄰的兩個關(guān)鍵字大小，若為反序咋交換。經(jīng)過一趟起泡后，關(guān)鍵詞大的必須移到最后。按照這種方式進(jìn)行第一趟在

7、序列（I[0]~I[n-1]）中從前往后進(jìn)行兩個相鄰元素的比較，若后者小，則交換，比較n-1次；第一趟排序結(jié)束，最大元素被交換到I[n-1]中，下一趟只需在子序列（I[0]~I[n-2]）中進(jìn)行；如果在某一趟排序中未交換元素，則不再進(jìn)行下一趟排序。將被排序的記錄數(shù)組J[1…n]垂直排列，每個記錄J[i]看作是重量為J[i].key的氣泡。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R：凡掃描到違反本原則的輕氣泡，就使其向上"飄浮"。如此反復(fù)進(jìn)行，直到最后任何兩個氣泡都是輕者在上，重者在下為止，最后可完成。（2）時間復(fù)雜度