排序算法比較

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

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

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

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

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