排序算法時間復雜度比較試驗設計

任洛漪 電子科技大學成都學院 計算機系

1 引言

各種排序算法時間復雜度比較部分是《數據結構》課程的重難點。如果光講理論，學生理解比較膚淺，因此我們嘗試在教學中用實驗的方法讓學生切身感受到各種排序算法的區別。

2 時間測量方法的準備

首先需要找到精確的時間測量方法。

常規的計時用是頭文件中的clock()函數，精度為1ms，但對于插入排序和冒泡排序對1000 個正序序列排序的情況，耗時只有幾十微秒，故需要設計精確到微秒的測量方式。

代碼如下

double run_time；

_LARGE_INTEGER time_start；

_LARGE_INTEGER time_over；

double dpFreq；

_LARGE_INTEGER f；

void StartTimer() {

QueryPerformanceCounter(&f)；

dpFreq = (double)f.QuadPart；

QueryPerformanceCounter(&time_start)；}

void EndTimer() {

QueryPerformanceCounter(&time_over)；

run_time = 1000000 * (time_over.QuadPart - time_start.QuadPart) / dpFreq；}

實際使用中，在做排序之前調用StartTimer()開始計時，排序之后立刻調用EndTimer()結束計時。時間間隔記錄到全局變量run_timer 中。

3 測試數據的準備

由于初始記錄的關鍵字的分布情況不同，排序算法的耗時也不同。故需要準備以下三種序列。

a)、正序初始序列，存放關鍵字遞增的數據序列。

b)、逆序初始序列，存放關鍵字遞減的數據序列。注意，由于排序基本都是原地重排，為了避免上一次排序的干擾，每次對逆序序列排序之前都必須重新生成逆序序列。

c)、隨機數初始序列，存放關鍵字為隨機數的數據序列。隨機序列進行比較之前需要生成一個隨機序列并將其復制多份，每個排序方式排一份數據，以便讓每種排序方法都針對相同序列并互不干擾。

4 實驗設計

基于以問題為導向，試驗將回答以下問題：

（1）對于正序序列的表，最省時間的排序方式為哪種算法？最費時間的又是哪種算法？

為此我們設計了了下列實驗，首先對正序序列賦值，然后使用直接插入排序、冒泡排序、簡單選擇排序、快速排序、堆排序、兩路歸并排序分別對該序列進行排序。并分別計時，生成結果如下：

圖1 正序序列情況下各種排序算法時間復雜度比較

可見，冒泡排序只需0.026 毫秒，在六種排序算法中耗時最少，因為正序情況下，它的時間復雜度為O(n)。

同時可見，與冒泡法時間復雜度相同的直接插入法，耗時更大。因為雖然執行次數相同，但每次循環中，直接插入法的還需執行移動，而同等情況下冒泡算法幾乎沒有移動次數，故速度更快。

并且對于正序序列，基準為第一個元素的快速排序并不占優勢，它的耗時僅次于簡單選擇排序，因為這種情況下，快速排序對應的二叉排序樹退化為一顆單枝樹，時間復雜度為O(n2)。

對于正序序列，最費時的是簡單選擇，因為同樣的實際復雜度O(n2)下，它的比較次數比快速排序要多。

（2）對于逆序序列，哪種算法最耗時？哪種最省時？實驗結果為

圖2 逆序序列情況下各種排序算法時間復雜度比較

可見，對于1000 個數的逆序序列，堆排序和歸并排序時間性能最好，時間復雜度為O(nlog2n)。直接插入，冒泡，簡單選擇和快速排序的耗時較長，時間復雜度都為O(n2)。

在后四個算法中，最快的是選擇排序，因其移動的次數最少。快速排序在這種情況下比較和移動的次數類似于選擇排序，但由于使用遞歸需要系統分配時間調用遞歸棧，所以耗時比選擇排序略高。冒泡和插入由于在逆序情況下移動和比較的次數都達到了最大值，所以排序性能不好。

（3）對于隨機序列，哪種算法最耗時？哪種最省時？實驗結果為

圖3 隨機序列情況下各種排序算法時間復雜度比較

可見，對于1000 個數以內的隨機序列，快速排序、堆排序和歸并排序時間性能最好。因為這種情況下，時間復雜度為O(nlog2n)。直接插入，冒泡，簡單選擇的耗時都較長，因為這種情況下時間復雜度都為O(n2)。

5 結論

通過實驗，學生對下圖各種排序的時間性能有了更直觀和深入的理解。教學收到了較好的效果。