排序算法比較

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

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

3、也是指向一維數組的指針在調用一次排序算法后通過形參對指針的改變被排序對象已經是有序的了.當再一次用其他排序算法后有可能比較次數和移動次數達到最大或最小.無論是哪種情況都是不好的這樣一來就失去了算法復雜度的比較意義了.為了避免這種情況的出現本程序采用在排序前新建一個數組將保存隨機數的數組復制到該數組讓排序算法對該數組進行排序.這樣就不會改變原始對象的隨機性.在統計排序算法運行時間時采用新建兩個time_t對象，排序開始前接收一次系統時間，

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

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