強(qiáng)振平，肖晨亮，李時(shí)雨，李俊萩

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

0 引言

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

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

1 排序算法簡介

1.1 排序的基本概念

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

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

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

1.2 排序算法分類

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

圖1 常用排序算法分類

首先，對(duì)各類排序算法的實(shí)現(xiàn)原理進(jìn)行簡略說明（以升序?yàn)槔?/p>

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

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

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

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

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

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

雖然幾乎所有的教材都給出類似于表1 的結(jié)果，但是對(duì)于學(xué)生來講，各種算法的具體執(zhí)行性能依然不夠直觀，實(shí)用情況也不清楚?；诖耍覀?cè)O(shè)計(jì)了常用排序算法性能分析平臺(tái)。

2 實(shí)驗(yàn)平臺(tái)設(shè)計(jì)

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

圖2 排序算法比較實(shí)驗(yàn)平臺(tái)設(shè)計(jì)思路

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

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

3 排序算法性能分析比較

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

表2 常見排序算法的適用情況對(duì)比

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