排序算法比較

1、一一排序算法比較排序算法比較1.問題描述對直接插入排序直接選擇排序冒泡排序快速排序堆排序五種排序算法進(jìn)行比較.要求:1.被排序的對象由計算機(jī)隨機(jī)生成分別取長度為5002000010000002.算法中增加比較移動次數(shù)和比較次數(shù)的統(tǒng)計功能并統(tǒng)計在排序同一組隨機(jī)數(shù)時每種排序算法的運(yùn)行時間及占用內(nèi)存情況.3.對實(shí)驗(yàn)的結(jié)果進(jìn)行比較2.設(shè)計思路這是一個算法性能評價程序重點(diǎn)在于算法性能的評價上.實(shí)現(xiàn)某一功能可能有很多方法判斷一個算法好壞的標(biāo)準(zhǔn)主要有

2、時間復(fù)雜度和空間復(fù)雜度.在當(dāng)今系統(tǒng)資源相對充足的計算機(jī)系統(tǒng)中時間復(fù)雜度變成了頭等問題.對于每一個排序算法都應(yīng)該有兩個返回值:比較次數(shù)和移動次數(shù).但在C語言中只能有一個函數(shù)返回值故這里采用指針傳遞地址的方式通過形參的地址從而可以修改實(shí)參值.這樣一來在每個排序算法參數(shù)列表中除了含被排序指針對象外另外加兩個整型變量指針用于傳遞算法執(zhí)行過程中的比較次數(shù)和移動次數(shù).取一定長度的對象由計算機(jī)產(chǎn)生一定量的偽隨機(jī)數(shù)后主函數(shù)調(diào)用各個排序函數(shù)但由于排序?qū)ο?/p>

3、也是指向一維數(shù)組的指針在調(diào)用一次排序算法后通過形參對指針的改變被排序?qū)ο笠呀?jīng)是有序的了.當(dāng)再一次用其他排序算法后有可能比較次數(shù)和移動次數(shù)達(dá)到最大或最小.無論是哪種情況都是不好的這樣一來就失去了算法復(fù)雜度的比較意義了.為了避免這種情況的出現(xiàn)本程序采用在排序前新建一個數(shù)組將保存隨機(jī)數(shù)的數(shù)組復(fù)制到該數(shù)組讓排序算法對該數(shù)組進(jìn)行排序.這樣就不會改變原始對象的隨機(jī)性.在統(tǒng)計排序算法運(yùn)行時間時采用新建兩個time_t對象，排序開始前接收一次系統(tǒng)時間，

4、排序結(jié)束后接收一次系統(tǒng)時間，二者的差值即為排序算法所運(yùn)行的時間。在每一趟冒泡排序中，依次比較相鄰兩個關(guān)鍵字的大小。若為反序，則交換。經(jīng)過一趟冒泡后最大的關(guān)鍵字已經(jīng)到達(dá)最后了。若按這種方法進(jìn)行n1趟冒泡，排序既能完成。(4)堆排序函數(shù)Heapst()對排序的算法思想很簡單，就是每次把關(guān)鍵字調(diào)整為堆，取出堆頂元素與最后一個元素交換，同時令堆的大小減一，把剩下的元素重新調(diào)整為堆，重復(fù)此過程，直到只剩下一個元素為止。(5)快速排序函數(shù)將帶排序記

5、錄的第一個記錄作為分區(qū)標(biāo)準(zhǔn)，將小于其的元素放在左邊，將大于其的元素放在右邊，中間放所選記錄，為一趟快速排序。然后對兩個子序列如此排序，直至所有記錄有序。5.程序代碼#include“stdafx.h“#include“stdio.h“#include“stdlib.h“#include“time.h“#include“windows.h“#include“psapi.h“#include“iostream“usingnamespaces