常用排序算法性能分析平臺的設(shè)計及結(jié)果分析＊

強振平，肖晨亮，李時雨，李俊萩

(西南林業(yè)大學(xué)大數(shù)據(jù)與智能工程學(xué)院，云南 昆明 650224)

0 引言

排序是計算機科學(xué)的重要內(nèi)容，是計算機及相關(guān)專業(yè)的學(xué)生必須掌握的一類基礎(chǔ)算法[1]。排序算法的應(yīng)用[2,3]有很多，常見的有插入排序、選擇排序、交換排序和歸并排序等多種排序方法。

在“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)中，一般要求學(xué)生將數(shù)據(jù)結(jié)構(gòu)與算法的理論運用到編程實踐中，讓學(xué)生體會數(shù)據(jù)結(jié)構(gòu)在實際應(yīng)用中的重要作用[4]。而由于“數(shù)據(jù)結(jié)構(gòu)”課程的描述大多是抽象形式，實現(xiàn)過程多以簡單示例為主，造成學(xué)生的學(xué)習(xí)困難。這就對“數(shù)據(jù)結(jié)構(gòu)”課程的實驗教學(xué)提出了更高的要求，學(xué)生需要通過編寫程序代碼將所學(xué)的理論知識融會貫通。對于排序算法，教師通過設(shè)計實驗，使得學(xué)生能夠?qū)Σ煌判蛩惴ǖ奶攸c深入理解，重視編程邏輯思維的培養(yǎng)，在遇到實際問題時，合理地選擇排序算法[5]。因此，本文從不同等級的數(shù)據(jù)量、不同初始排序序列的數(shù)據(jù)為出發(fā)點設(shè)計排序?qū)嶒灒ΤＳ门判蛩惴ǖ膱?zhí)行時間、比較次數(shù)和移動次數(shù)進行分析比較，直觀地反映各種排序算法優(yōu)缺點，對學(xué)生深刻地認(rèn)識和理解排序算法有著重要的意義。

1 排序算法簡介

1.1 排序的基本概念

關(guān)鍵字[6]：關(guān)鍵字是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用它可以標(biāo)識一個數(shù)據(jù)元素（或記錄）。

排序[7]：按關(guān)鍵字的非遞減或非遞增順序?qū)σ唤M數(shù)據(jù)重新進行排列的操作。

排序的穩(wěn)定性[7]：若排序前后關(guān)鍵字相同的數(shù)據(jù)相對位置不發(fā)生變化，則稱所用的排序算法是穩(wěn)定的，否則就是不穩(wěn)定的。

1.2 排序算法分類

按照排序方式的不同，常用的排序算法可分為四類（如圖1所示），按照每類排序算法的思想，又包括一些不同算法，本文針對這四類中八個具體的算法進行分析。

圖1 常用排序算法分類

首先，對各類排序算法的實現(xiàn)原理進行簡略說明（以升序為例）。

⑴插入排序，先把原序列分為有序子序列（開始時只有一個數(shù)據(jù)元素）和無序子序列，然后每輪循環(huán)從無序序列中取出一個數(shù)據(jù)元素，插入到有序子序列的合適位置，直到無序子序列為空為止。

⑵選擇排序，先把原序列分為有序子序列（開始時為空）和無序子序列，循環(huán)從未排序子序列中選出最小數(shù)據(jù)元素加入到有序子序列中。

⑶交換排序：把原序列分為有序子序列（初始為空）和無序子序列，循環(huán)將每個數(shù)據(jù)交換到正確位置。

⑷歸并排序：采用分而治之的思想，依次將兩個或兩個以上的有序序列合并成一個有序序列。其中，最常用的就是二路歸并排序，即將一個待排序的序列分成兩個序列，分別對這兩個序列排序。而對于這兩個序列排序的方式也是將這兩個序列分別分成兩個序列分別排序。

根據(jù)不同排序算法的實現(xiàn)原理和實現(xiàn)步驟，可以推導(dǎo)出各排序算法的時間復(fù)雜度，空間復(fù)雜度及穩(wěn)定性等性質(zhì)。參見表1。

表1 常見排序算法的性質(zhì)對比

雖然幾乎所有的教材都給出類似于表1 的結(jié)果，但是對于學(xué)生來講，各種算法的具體執(zhí)行性能依然不夠直觀，實用情況也不清楚。基于此，我們設(shè)計了常用排序算法性能分析平臺。

2 實驗平臺設(shè)計

為了更加直觀地感受不同排序算法在不同待排序數(shù)據(jù)情況下的執(zhí)行效率以及發(fā)現(xiàn)哪些因素是影響排序算法執(zhí)行效率的關(guān)鍵因素。實驗實現(xiàn)八種排序算法，并用不同數(shù)據(jù)規(guī)模和不同初始化排序狀態(tài)的待排序數(shù)據(jù)進行實驗，將每次算法的執(zhí)行時間、比較次數(shù)和移動次數(shù)記錄并進行可視化分析。實驗平臺的設(shè)計思路如圖2所示。

圖2 排序算法比較實驗平臺設(shè)計思路

執(zhí)行程序時，需要從控制臺輸入待排序的數(shù)據(jù)規(guī)模和選擇隨機、正序或逆序生成待排序的數(shù)據(jù)元素，程序會在執(zhí)行每個排序函數(shù)之前對數(shù)據(jù)進行恢復(fù)，保證每個排序函數(shù)對相同的數(shù)據(jù)進行排序，滿足比較的公平性。所有排序方法執(zhí)行完畢后，控制臺打印每個排序算法的執(zhí)行時間、比較次數(shù)和移動次數(shù)。同時將輸出數(shù)據(jù)寫入文件，便于進一步可視化分析。

實驗過程采用了基于x86_64架構(gòu)服務(wù)器，CPU 為Intel Xeon E5-2683V3 2.00GHz，運行內(nèi)存64GB，采用Ubuntu操作系統(tǒng)，版本號為16.04.1。采用C 語言對8 種排序算法進行了編程實現(xiàn)，其中代碼已盡可能精簡，減少冗余。完整的代碼可以在https://github.com/qzplucky/SortCompare下載。

3 排序算法性能分析比較

通過變量確定數(shù)據(jù)元素數(shù)量和數(shù)據(jù)初始化狀態(tài)（包括了隨機、正序和逆序三種方式），在確定的數(shù)據(jù)初始狀態(tài)下分析多種數(shù)據(jù)規(guī)模時每種算法的執(zhí)行效率，得出在該數(shù)據(jù)狀態(tài)下不同算法的優(yōu)劣；相同的數(shù)據(jù)排序時，分析排序時間與比較次數(shù)和移動次數(shù)的關(guān)系；在相同的數(shù)據(jù)規(guī)模時，分析哪種排序算法的排序效率更容易受到數(shù)據(jù)初始狀態(tài)的影響。

3.1 隨機初始化狀態(tài)下不同數(shù)據(jù)規(guī)模各種排序算法的時間效率

在實際工作中，需要排序的數(shù)據(jù)絕大部分情況下滿足隨機分布（可以認(rèn)為是無序的），因而無序狀態(tài)下排序算法的效率最能體現(xiàn)出該算法的平均效率。無序狀態(tài)下不同數(shù)據(jù)規(guī)模時各排序算法的執(zhí)行時間如圖3所示。

圖3 隨機初始化不同數(shù)據(jù)規(guī)模時各種排序算法執(zhí)行時間比較

因各種算法在有些情況下執(zhí)行時間差異非常大，所以在時間比較過程中縱坐標(biāo)軸采用了對數(shù)刻度。在隨機初始化序列的狀態(tài)下，當(dāng)待排序的數(shù)據(jù)規(guī)模小于等于1萬時，各排序算法的執(zhí)行時間沒有太大區(qū)別，執(zhí)行時間都是在1秒鐘之內(nèi)。而當(dāng)待排序的數(shù)據(jù)規(guī)模大于等于10萬時，冒泡排序、直接插入排序、簡單選擇排序和二分插入排序的排序時間迅速增加，特別是當(dāng)數(shù)據(jù)規(guī)模達(dá)到100 萬時，他們的執(zhí)行時間都達(dá)到了1,000 秒，冒泡排序甚至接近100,000 秒。數(shù)據(jù)規(guī)模達(dá)到1,000 萬時，這幾個排序算法的執(zhí)行時間是讓人難以接受的，也沒有顯示的意義，因此，在圖3 中未加以顯示。對于希爾排序、堆排序、二路歸并排序和快速排序，當(dāng)數(shù)據(jù)規(guī)模達(dá)到100萬時，排序時間仍保持在1秒之內(nèi)，當(dāng)數(shù)據(jù)規(guī)模達(dá)到1,000 萬時，四個排序算法中除希爾排序外其他排序算法排序時間保持在10秒之內(nèi)。尤其是二路歸并排序及快速排序，即使數(shù)據(jù)規(guī)模達(dá)到2,000萬時，排序時間仍然保持在10秒之內(nèi)。

因此，在隨機初始化序列狀態(tài)時，當(dāng)數(shù)據(jù)規(guī)模小于等于1萬時，排序算法對排序效率沒有太大的影響。這時，原理簡單，容易編程實現(xiàn)的冒泡排序和直接插入排序是可行的。當(dāng)在數(shù)據(jù)規(guī)模到10萬以上時，選擇希爾排序、堆排序、二路歸并排序和快速排序能顯著地提高排序效率。其中，二路歸并排序及快速排序的是排序效率最高的算法。

3.2 正序狀態(tài)下不同數(shù)據(jù)規(guī)模各種排序算法的時間效率

在待排序數(shù)據(jù)為正序的情況下用不同數(shù)據(jù)規(guī)模的數(shù)據(jù)對排序算法進行性能測試，所得結(jié)果可以為在數(shù)據(jù)基本有序的情況下選擇合適的排序算法的依據(jù)。正序狀態(tài)下不同數(shù)據(jù)規(guī)模時的排序算法執(zhí)行時間如圖4所示。

圖4 正序初始化不同數(shù)據(jù)規(guī)模時各種排序算法執(zhí)行時間比較

由圖4可見，在正序狀態(tài)下，當(dāng)數(shù)據(jù)規(guī)模小于等于1 萬時，同隨機狀態(tài)下一樣，各種排序算法的執(zhí)行時間沒有太大的區(qū)別，都是在1 秒鐘之內(nèi)。當(dāng)數(shù)據(jù)規(guī)模大于等于20萬時，快速排序與簡單選擇排序所需時間大幅度上升，當(dāng)數(shù)據(jù)規(guī)模達(dá)到100萬時，這兩個排序算法所需時間達(dá)到了1000 秒，當(dāng)數(shù)據(jù)規(guī)模達(dá)到1000 萬時，這兩個排序算法的執(zhí)行時間已讓人難以接受，故圖4中未進行展示。而其他六個算法始終保持著高效率，在數(shù)據(jù)規(guī)模達(dá)到2000 萬時仍然能在10 秒內(nèi)執(zhí)行完畢，尤其是直接插入排序和冒泡排序（程序中判定了序列情況，設(shè)計了提前結(jié)束排序操作），可以在不到1 秒的時間完成。所以，當(dāng)數(shù)據(jù)基本有序時，選擇直接插入排序和冒泡排序是比較好的選擇。

將圖3 與圖4 對比，可以發(fā)現(xiàn)，正序狀況下同等數(shù)據(jù)規(guī)模時，大多數(shù)排序算法在所需時間相比于隨機狀態(tài)下所需時間更短，效率更高。且冒泡排序、直接插入排序和二分插入排序時間縮短明顯，而在隨機狀態(tài)下效率最高的快速排序卻在正序狀況下耗時大幅度上升。這個現(xiàn)象將在后文通過對比較次數(shù)和移動次數(shù)的分析加以解釋。

3.3 逆序狀態(tài)下不同數(shù)據(jù)規(guī)模各種排序算法的時間效率

在待排序數(shù)據(jù)為逆序的情況下用不同數(shù)據(jù)規(guī)模的數(shù)據(jù)對排序算法進行性能測試，可為我們在待排序數(shù)據(jù)為逆序時選擇排序算法提供參考。逆序狀態(tài)下不同數(shù)據(jù)規(guī)模時的排序執(zhí)行時間如圖5所示。

通過將圖5 與圖3 對比可以發(fā)現(xiàn)，在在逆序狀況下各排序算法的執(zhí)行效率與在隨機狀態(tài)下基本相同，堆排序、希爾排序和二路歸并排序仍然時排序效率最高的三種排序算法。

圖5 逆序初始化不同數(shù)據(jù)規(guī)模時各種排序算法執(zhí)行時間比較

所以，當(dāng)數(shù)據(jù)基本上為逆序時，選擇堆排序、希爾排序和二路歸并排序是比較好的選擇。

而逆序狀況下的快速排序卻同在正序狀況下一致，對相同規(guī)模的數(shù)據(jù)進行排序時，排序時間遠(yuǎn)遠(yuǎn)高于在隨機序列狀況下排序時間。同樣，這個現(xiàn)象將在后文通過對比較次數(shù)和移動次數(shù)的分析加以解釋。

3.4 算法執(zhí)行時間與比較次數(shù)、移動次數(shù)之間的關(guān)系

正確認(rèn)識排序算法執(zhí)行時間與算法運行過程中比較次數(shù)、移動次數(shù)之間的關(guān)系，能為選擇合適的排序算法以及創(chuàng)建新的高效率的排序算法提供依據(jù)。綜合分析隨機狀態(tài)下數(shù)據(jù)規(guī)模為100萬時的排序執(zhí)行時間與比較次數(shù)、移動次數(shù)及兩個次數(shù)的總和的關(guān)系如圖6所示。

圖6 隨機狀態(tài)下100萬數(shù)據(jù)規(guī)模時排序算計時間與比較次數(shù)、移動次數(shù)比較圖

通過對圖6 的分析，驗證了排序算法的執(zhí)行時間與所需的比較次數(shù)和移動次數(shù)總合存在正相關(guān)關(guān)系，而與單獨的比較次數(shù)或移動次數(shù)沒有直接關(guān)系。因此，當(dāng)一個排序算法在排序過程中所需的比較次數(shù)和移動次數(shù)總合越小時，所需的排序時間就會越短，排序效率也就越高，這也是我們選擇和設(shè)計排序算法的重要依據(jù)。

3.5 不同數(shù)據(jù)初始狀況下排序時間與比較次數(shù)、移動次數(shù)總和的分析

通過排序算法執(zhí)行時間與比較次數(shù)、移動次數(shù)之間的關(guān)系可知排序時間與比較次數(shù)、移動次數(shù)總和存在正相關(guān)關(guān)系。解釋說明了不同初始狀況下某些排序算法的執(zhí)行效率會發(fā)生明顯差異，便于認(rèn)識不同排序算法在不同數(shù)據(jù)初始狀況下的排序效率。故對100萬數(shù)據(jù)規(guī)模時不同數(shù)據(jù)初始狀況下排序時間與比較次數(shù)、移動次數(shù)總合進行分析，如圖7所示。

圖7 隨機狀態(tài)下100萬數(shù)據(jù)規(guī)模時排序算法執(zhí)行時間與比較次數(shù)、移動次數(shù)比較圖

從圖7可知，冒泡排序、直接插入排序和二分插入排序因為在對正序狀態(tài)下的數(shù)據(jù)進行排序時執(zhí)行的比較次數(shù)和移動次數(shù)總和非常低，所以在待排序數(shù)據(jù)為正序時，執(zhí)行效率非常高。而希爾排序在對正序狀態(tài)和逆序狀態(tài)下的數(shù)據(jù)進行排序時執(zhí)行的比較次數(shù)和移動次數(shù)總和非常高，所以在待排序數(shù)據(jù)為正序或逆序時，執(zhí)行效率相對較低。

就同一個排序算法對不同初始狀態(tài)的數(shù)據(jù)進行排序所需時間可以發(fā)現(xiàn)，冒泡排序、直接插入排序、二分插入排序只在待排序數(shù)據(jù)為正序時效率比較高，快速排序只在待排序數(shù)據(jù)為隨機序列時效率較高，希爾排序、堆排序、二路歸并排序在三種數(shù)據(jù)初始狀況下效率都比較高，而簡單選擇排序在三種數(shù)據(jù)初始狀況下效率都比較低。

4 結(jié)束語

本文對八種常見的排序算法進行了簡略的理論介紹，重點設(shè)計了在不同數(shù)據(jù)規(guī)模、不同數(shù)據(jù)初始化狀態(tài)下的各個排序算法的執(zhí)行效率和比較、移動次數(shù)的比較分析，結(jié)論對理論知識的理解和掌握具有明顯的促進作用。

不同的排序算法各有優(yōu)劣，在選擇排序算法時應(yīng)綜合考慮待排序數(shù)據(jù)的數(shù)據(jù)規(guī)模和數(shù)據(jù)分布情況，排序算法的執(zhí)行效率和穩(wěn)定性。基于實驗結(jié)果，常用排序算法的適用情況總結(jié)如表2所示。

表2 常見排序算法的適用情況對比

陳國良院士指出，計算思維的第一功能是提出問題的解決方案和設(shè)計系統(tǒng)[8]，本文的實驗設(shè)計，從排序算法理論為出發(fā)點，提出了針對性的如何評價排序算法這一問題，針對該問題，設(shè)計了包括不同初始化序列、不同數(shù)據(jù)規(guī)模的比較實驗，對算法的執(zhí)行時間，算法中涉及的數(shù)據(jù)元素比較次數(shù)、移動次數(shù)進行統(tǒng)計分析。這一過程有助于學(xué)生深入理解理論知識、增加實際動手能力，同時，可以促進學(xué)生主動學(xué)習(xí)，將數(shù)據(jù)結(jié)構(gòu)中的算法靈活應(yīng)用于實際解決問題的實踐中。