排序算法時(shí)間復(fù)雜度比較試驗(yàn)設(shè)計(jì)

任洛漪 電子科技大學(xué)成都學(xué)院 計(jì)算機(jī)系

1 引言

各種排序算法時(shí)間復(fù)雜度比較部分是《數(shù)據(jù)結(jié)構(gòu)》課程的重難點(diǎn)。如果光講理論，學(xué)生理解比較膚淺，因此我們嘗試在教學(xué)中用實(shí)驗(yàn)的方法讓學(xué)生切身感受到各種排序算法的區(qū)別。

2 時(shí)間測量方法的準(zhǔn)備

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

常規(guī)的計(jì)時(shí)用是頭文件中的clock()函數(shù)，精度為1ms，但對于插入排序和冒泡排序?qū)?000 個(gè)正序序列排序的情況，耗時(shí)只有幾十微秒，故需要設(shè)計(jì)精確到微秒的測量方式。

代碼如下

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；}

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

3 測試數(shù)據(jù)的準(zhǔn)備

由于初始記錄的關(guān)鍵字的分布情況不同，排序算法的耗時(shí)也不同。故需要準(zhǔn)備以下三種序列。

a)、正序初始序列，存放關(guān)鍵字遞增的數(shù)據(jù)序列。

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

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

4 實(shí)驗(yàn)設(shè)計(jì)

基于以問題為導(dǎo)向，試驗(yàn)將回答以下問題：

（1）對于正序序列的表，最省時(shí)間的排序方式為哪種算法？最費(fèi)時(shí)間的又是哪種算法？

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

圖1 正序序列情況下各種排序算法時(shí)間復(fù)雜度比較

可見，冒泡排序只需0.026 毫秒，在六種排序算法中耗時(shí)最少，因?yàn)檎蚯闆r下，它的時(shí)間復(fù)雜度為O(n)。

同時(shí)可見，與冒泡法時(shí)間復(fù)雜度相同的直接插入法，耗時(shí)更大。因?yàn)殡m然執(zhí)行次數(shù)相同，但每次循環(huán)中，直接插入法的還需執(zhí)行移動(dòng)，而同等情況下冒泡算法幾乎沒有移動(dòng)次數(shù)，故速度更快。

并且對于正序序列，基準(zhǔn)為第一個(gè)元素的快速排序并不占優(yōu)勢，它的耗時(shí)僅次于簡單選擇排序，因?yàn)檫@種情況下，快速排序?qū)?yīng)的二叉排序樹退化為一顆單枝樹，時(shí)間復(fù)雜度為O(n2)。

對于正序序列，最費(fèi)時(shí)的是簡單選擇，因?yàn)橥瑯拥膶?shí)際復(fù)雜度O(n2)下，它的比較次數(shù)比快速排序要多。

（2）對于逆序序列，哪種算法最耗時(shí)？哪種最省時(shí)？實(shí)驗(yàn)結(jié)果為

圖2 逆序序列情況下各種排序算法時(shí)間復(fù)雜度比較

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

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

（3）對于隨機(jī)序列，哪種算法最耗時(shí)？哪種最省時(shí)？實(shí)驗(yàn)結(jié)果為

圖3 隨機(jī)序列情況下各種排序算法時(shí)間復(fù)雜度比較

可見，對于1000 個(gè)數(shù)以內(nèi)的隨機(jī)序列，快速排序、堆排序和歸并排序時(shí)間性能最好。因?yàn)檫@種情況下，時(shí)間復(fù)雜度為O(nlog2n)。直接插入，冒泡，簡單選擇的耗時(shí)都較長，因?yàn)檫@種情況下時(shí)間復(fù)雜度都為O(n2)。

5 結(jié)論

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