黎佩南（中國(guó)西南電子技術(shù)研究所，成都610036）

一種快速排序算法的實(shí)現(xiàn)及其應(yīng)用?

黎佩南
（中國(guó)西南電子技術(shù)研究所，成都610036）

介紹了一種快速的排序方法——堆排序。以一個(gè)簡(jiǎn)單的實(shí)例結(jié)合完全二叉樹(shù)說(shuō)明了該算法的原理，給出了利用C語(yǔ)言實(shí)現(xiàn)該算法的代碼，從時(shí)間復(fù)雜度和輔助存儲(chǔ)空間的角度分析了與其他排序算法相比較的優(yōu)劣。實(shí)驗(yàn)表明，在對(duì)大量數(shù)據(jù)進(jìn)行排序時(shí)，堆排序算法效率較高。

排序算法；快速排序；堆排序；時(shí)間復(fù)雜度；輔助存儲(chǔ)空間

1 引言

排序（Sorting）是將一個(gè)數(shù)據(jù)元素的任意序列，按關(guān)鍵字的升序或降序重新排列成一個(gè)有序序列的過(guò)程［1］。有序序列為記錄的查找、插入和刪除提供了方便，可以有效提高效率。在現(xiàn)代工程中，排序被廣泛應(yīng)用于數(shù)據(jù)庫(kù)管理、網(wǎng)絡(luò)路由分配、信號(hào)處理、生物工程、人工智能、計(jì)算機(jī)圖形、計(jì)算機(jī)輔助設(shè)計(jì)、模式識(shí)別及統(tǒng)計(jì)學(xué)等各個(gè)領(lǐng)域。在計(jì)算機(jī)出現(xiàn)之前，排序是一項(xiàng)非常復(fù)雜而繁瑣的工作，完全依賴于人工，人們需要對(duì)每一份數(shù)據(jù)進(jìn)行逐一對(duì)比，要求參與者精神高度集中，而大量數(shù)據(jù)的排序往往會(huì)耗費(fèi)相當(dāng)長(zhǎng)的時(shí)間。在計(jì)算機(jī)出現(xiàn)后，由于其響應(yīng)快速、計(jì)算精密，排序已經(jīng)實(shí)現(xiàn)了完全由計(jì)算機(jī)自動(dòng)完成。本文介紹了一種快速的排序方法——堆排序（Heap

Sort），并利用C語(yǔ)言實(shí)現(xiàn)了該算法的代碼。該算法的特點(diǎn)是速度較快，占用的輔助空間小，尤其適用于大數(shù)據(jù)量記錄的排序。

2 排序算法簡(jiǎn)介

排序的方法有很多，按排序時(shí)訪問(wèn)的介質(zhì)，排序可分為內(nèi)部排序（整個(gè)排序過(guò)程不需要訪問(wèn)外部存儲(chǔ)器）和外部排序（參加排序的記錄數(shù)量很大，排序過(guò)程不可能在內(nèi)存中完成，需訪問(wèn)外部存儲(chǔ)器）。隨著計(jì)算機(jī)硬件技術(shù)的飛速發(fā)展，內(nèi)存空間不斷擴(kuò)展，外部排序的應(yīng)用已大大減少。內(nèi)部排序按所用策略不同，分為插入排序、選擇排序、交換排序、歸并排序和基數(shù)排序等［2］。

2.1 插入排序

常用的插入排序算法有直接插入排序和希爾排序。直接插入排序是最簡(jiǎn)單的排序方法，基本操作是將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增1的有序表。

希爾排序先將整個(gè)待排記錄序列分割為若干子序列分別進(jìn)行直接插入排序，待正序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。

2.2 交換排序

常用的交換排序算法有起泡排序和快速排序。

起泡排序又稱冒泡排序，也是一種簡(jiǎn)單的排序算法，在排序過(guò)程中，關(guān)鍵字較小的記錄隨著不斷交換逐漸前移。

快速排序是對(duì)起泡排序的一種改進(jìn)，通過(guò)一次排序?qū)⒂涗浄指畛瑟?dú)立的兩部分，其中一部分的關(guān)鍵字均比另一部分小，再分別對(duì)這兩部分記錄進(jìn)行排序，達(dá)到整個(gè)序列有序。

2.3 選擇排序

常用的選擇排序算法有直接選擇排序和堆排序。

直接選擇排序是通過(guò)n-i次關(guān)鍵字間的比較，從n-i+1個(gè)記錄中選取關(guān)鍵字最小的記錄，并與第i（1≤i≤n）個(gè)記錄交換。

堆排序是一種基于完全二叉樹(shù)對(duì)葉子節(jié)點(diǎn)進(jìn)行不斷篩選的排序過(guò)程。

2.4 歸并排序

將兩個(gè)或兩個(gè)以上的有序表組成一個(gè)新的有序表，先將n個(gè)數(shù)據(jù)看成n個(gè)長(zhǎng)度為1的表，將相鄰的表成對(duì)歸并，得到長(zhǎng)度為2的有序表，再將相鄰表歸并為長(zhǎng)度為4的有序表，依次做下去，直到所有數(shù)據(jù)均合并到一個(gè)長(zhǎng)度為n的有序表中［3］。

2.5 基數(shù)排序

基數(shù)排序是一種借助多關(guān)鍵字排序的思想對(duì)單邏輯關(guān)鍵字進(jìn)行排序的算法［2］。

插入排序、交換排序、選擇排序及歸并排序適用于單關(guān)鍵字的序列排序，基數(shù)排序則適用于多關(guān)鍵字的序列排序。

3 堆排序算法

堆排序算法是一種基于完全二叉樹(shù)和堆的排序算法。下面首先介紹完全二叉樹(shù)和堆的定義。

完全二叉樹(shù)是一種具有下列性質(zhì)的二叉樹(shù)：若已知某個(gè)結(jié)點(diǎn)編號(hào)為i，則有：若i=1，該結(jié)點(diǎn)為根結(jié)點(diǎn)；若結(jié)點(diǎn)i有左孩子，則其編號(hào)為2×i；若結(jié)點(diǎn)i有右孩子，則其編號(hào)為2×i+1。且N個(gè)結(jié)點(diǎn)的編號(hào)從1到N是連續(xù)的［4］。

堆的定義如下：n個(gè)元素的序列｛k1，k2，k3，…，kn｝，當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱之為堆［4］。

若將和此序列對(duì)應(yīng)的一維數(shù)組看作是一個(gè)完全二叉樹(shù)，則堆的含義表明，完全二叉樹(shù)中所有非終端節(jié)點(diǎn)的值均不大于（或不小于）其左、右子節(jié)點(diǎn)。因此，若序列｛k1，k2，k3，…，kn｝是堆，則堆頂元素（即該完全二叉樹(shù)的根）必為該序列中n個(gè)元素的最小值或最大值。圖1和圖2分別是兩個(gè)完全二叉樹(shù)，對(duì)應(yīng)的一維數(shù)組分別為｛96，83，27，38，11，09｝和｛12，

36，24，85，47，30，53，91｝。

在輸出堆頂?shù)淖畲螅ɑ蜃钚。┲抵?，剩余的n -1個(gè)元素的序列重新建成一個(gè)堆，則得到n個(gè)元素中的次大（或次?。┲?，如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列，這個(gè)過(guò)程就是堆排序。因此，實(shí)現(xiàn)堆排序需要解決兩個(gè)問(wèn)題：一是如何由一個(gè)無(wú)序序列建成一個(gè)堆；二是如何在輸出堆頂元素后，調(diào)整剩余元素成為一個(gè)新堆。下面分別描述兩個(gè)過(guò)程。由于建堆的過(guò)程需要一直用到過(guò)程2，因此首先介紹過(guò)程2。

3.1 推出堆頂及篩選

下面以圖2所示堆為例來(lái)說(shuō)明這一過(guò)程。

將堆頂?shù)?2推出，以堆底的91代替，如圖3（a）所示，此時(shí)根節(jié)點(diǎn)的左、右子樹(shù)均為堆，因此只需自上向下調(diào)整即可。此時(shí)比較堆頂元素及其左、右子樹(shù)的根節(jié)點(diǎn)，由于右子樹(shù)根節(jié)點(diǎn)比左子樹(shù)根節(jié)點(diǎn)及堆頂元素都小，因此將右根子樹(shù)節(jié)點(diǎn)與堆頂元素交換，剩余的調(diào)整過(guò)程在右子樹(shù)中進(jìn)行，如圖3（b）所示?？梢钥匆?jiàn)，在經(jīng)過(guò)多次調(diào)整之后，剩余的數(shù)又形成了一個(gè)新的堆，如圖3（c）所示。堆頂至葉子的調(diào)整過(guò)程稱之為“篩選”。重復(fù)執(zhí)行“推出堆頂數(shù)據(jù)→篩選”的過(guò)程，就可以得到一個(gè)有序的隊(duì)列。

3.2 建堆

從一個(gè)無(wú)序序列建堆的過(guò)程實(shí)際上就是一個(gè)反復(fù)“篩選”的過(guò)程。若將次序列看做一個(gè)完全二叉樹(shù)，則最后一個(gè)非終端節(jié)點(diǎn)是第n／2個(gè)元素，因此“篩選”只需從第n／2個(gè)元素開(kāi)始。下面將圖2中的樹(shù)稍作修改，以此為例說(shuō)明建一個(gè)升序堆的過(guò)程。初始序列樹(shù)如圖4所示。

篩選從第4個(gè)元素，即91開(kāi)始，91大于其子節(jié)點(diǎn)24，將兩者交換，結(jié)果如圖5所示；再篩選第三個(gè)元素53，結(jié)果如圖6所示；再篩選第二個(gè)元素85，結(jié)果如圖7所示；再篩選根節(jié)點(diǎn)36，結(jié)果如圖8和9所示。

經(jīng)過(guò)以上變換，一個(gè)符合條件的初始堆就建成了，堆頂元素12為堆中最小值，推出堆頂12后，再調(diào)整剩余的元素，就可以形成一個(gè)有序的序列。

通過(guò)以上分析可以看出，堆排序算法運(yùn)行時(shí)間主要耗費(fèi)在建初始堆和反復(fù)“篩選”的過(guò)程中。對(duì)深度為k的堆，“篩選”算法中進(jìn)行的關(guān)鍵字比較次數(shù)最多為2（k-1）次，n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)深度為lg n+1，調(diào)整新建堆時(shí)總共比較的總次數(shù)最多為

2（lg（n-1）+lg（n-2）+lg（n-3）+…+lg2）＜2 n lg n

由此可見(jiàn)，在最壞的情況下，其時(shí)間復(fù)雜度為n lg n［5］。同時(shí)，該算法在整個(gè)排序過(guò)程中，只需要一個(gè)額外的存儲(chǔ)控件，因此在進(jìn)行大數(shù)據(jù)量元素的排序時(shí)，堆排序算法是一個(gè)較好的選擇，但是堆排序算法相對(duì)來(lái)說(shuō)較為復(fù)雜，記錄數(shù)較少時(shí)不值得提倡。

4 代碼實(shí)現(xiàn)

下面給出利用C++Builder實(shí)現(xiàn)堆排序的代碼。

4.1 篩選

代碼如下：

void Sift（int iRootIndex，int iNodeCount）

／／iRootIndex為當(dāng)前根節(jié)點(diǎn)在序列中的位置，iNodeCount為剩余節(jié)點(diǎn)數(shù)量

｛

int iLeftLeave，iRightLeave；／／根節(jié)點(diǎn)的左右子節(jié)點(diǎn)

bool bFinish=false；／／排序完成標(biāo)志

int iRoot；／／根節(jié)點(diǎn)值

int iTemp；／／臨時(shí)變量，保存原始根節(jié)點(diǎn)

／／獲取當(dāng)前根節(jié)點(diǎn)值

iTemp=DataList［iRootIndex］；

iRoot=DataList［iRootIndex］；

／／獲取根節(jié)點(diǎn)的子節(jié)點(diǎn)

iLeftLeave=iRootIndex；

iRightLeave=2*iLeftLeave；

／／重新排列堆

while（iRightLeave＜=iNodeCount＆＆！bFinish）

｛

／／語(yǔ)句1：若存在右子樹(shù)，且右子樹(shù)根的值較小，則沿右子樹(shù)篩選，否則沿左子樹(shù)篩選

if（iRightLeave＜iNodeCount＆＆DataList［iRightLeave］＞DataList［iRightLeave+1］）

iRightLeave=iRightLeave+1；

／／語(yǔ)句2：若根節(jié)點(diǎn)的值較小，篩選完成，否則繼續(xù)篩選

if（iTemp＜=DataList［iRightLeave］）

bFinish=true；

else

｛

iLeftLeave=iRightLeave；

iRightLeave=2*iLeftLeave；

｝

｝

／／根節(jié)點(diǎn)插入恰當(dāng)位置

DataList［iLeftLeave］=iRoot；

｝

4.2 堆排序

代碼如下：

void HeapSortAsdc（void）

｛

／／對(duì)DataList中的數(shù)據(jù)從第n／2個(gè)記錄開(kāi)始進(jìn)行篩選建堆

for（i=（（i＞iCount-1）／2）；i＞=0；i--）

Sift（i，iCount-1）；

for（i=iCount-1；i＞=1；i--）

｛

／／將堆頂數(shù)據(jù)與最后一個(gè)數(shù)據(jù)互換，使堆頂數(shù)據(jù)被推出

Exchange（DataList，0，i）；

／／調(diào)整剩余的數(shù)據(jù)，使之成為一個(gè)堆

Sift（0，i-1）；

｝

｝

說(shuō)明：

（1）DataList是一個(gè)整型數(shù)組，事先已裝載了待排序的數(shù)據(jù)，iCount為DataList中元素的個(gè)數(shù)；

（2）Exchange（i，j）用于實(shí)現(xiàn)數(shù)組相應(yīng)位置數(shù)據(jù)的交換；

（3）上述算法是針對(duì)整數(shù)進(jìn)行排序，若要實(shí)現(xiàn)對(duì)其他類型，如浮點(diǎn)數(shù)、字符的排序，只需將DataList改為相應(yīng)的數(shù)組；

（4）該算法由標(biāo)準(zhǔn)C語(yǔ)言實(shí)現(xiàn)，可以用于DSP、MATLAB及VxWorks嵌入式操作系統(tǒng)等；

（5）由于每次推出的堆頂元素都被排在序列的首部，因此上述代碼實(shí)現(xiàn)的是降序排序，只需將語(yǔ)句1和語(yǔ)句2中相應(yīng)的大于或小于比較符進(jìn)行相應(yīng)修改，即可實(shí)現(xiàn)升序排序；

（6）以上代碼是將待排序數(shù)據(jù)存放在數(shù)組中，在排序過(guò)程中需要進(jìn)行記錄的移動(dòng)，適用于記錄較?。疵總€(gè)記錄占用的空間較?。┑那闆r，若記錄很大，移動(dòng)記錄的時(shí)間消耗也較大，這時(shí)可利用鏈表和指針來(lái)存儲(chǔ)數(shù)據(jù)，以修改指針代替移動(dòng)記錄，以提高效率。

5 算法比較與分析

排序算法多種多樣，在實(shí)際應(yīng)用中選擇哪種算法，主要是參考其時(shí)間復(fù)雜度（Time Complexity）和空間復(fù)雜度（Space Complexity）。時(shí)間復(fù)雜度是指完成一個(gè)算法所需要的時(shí)間的量度，空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間的大小的量度，這兩者都是衡量一個(gè)算法優(yōu)劣的重要參數(shù)。下面用表1來(lái)簡(jiǎn)單比較各種排序方法。

由表1可以看出，因其本身的時(shí)間復(fù)雜度和占用的輔助空間，每種排序算法各有其優(yōu)缺點(diǎn)及適應(yīng)性。為了更直觀地說(shuō)明堆排序在時(shí)間復(fù)雜度上的優(yōu)勢(shì)，在一臺(tái)主頻2.8 GHz、內(nèi)存512 MB的計(jì)算機(jī)上，利用C實(shí)現(xiàn)了直接插入排序、希爾排序、起泡排序和堆排序等算法，并對(duì)不同數(shù)量的記錄進(jìn)行了排序，實(shí)驗(yàn)結(jié)果如表2所示。

由表2可以看出，簡(jiǎn)單的算法，隨著記錄數(shù)的增加，時(shí)間的消耗將會(huì)大大增加，此類算法只適用于記錄數(shù)較少的序列。而堆排序算法雖然復(fù)雜度高，在對(duì)記錄較少的序列排序時(shí)，未免顯得大材小用，但是在對(duì)大量數(shù)據(jù)進(jìn)行排序時(shí)，優(yōu)勢(shì)非常明顯。例如在工程中常常使用的數(shù)據(jù)庫(kù)檢索排序，當(dāng)記錄數(shù)達(dá)到一定的數(shù)量級(jí)，如萬(wàn)條時(shí)，排序時(shí)間往往成為瓶頸，過(guò)長(zhǎng)的等待時(shí)間使用戶難以忍受，而堆排序算法的高效性很好地解決了這個(gè)問(wèn)題。在實(shí)際應(yīng)用中，還可以將堆排序與其他算法結(jié)合使用，以使時(shí)間和空間的效率達(dá)到最優(yōu)。

［1］Thomas H Cormen，Charles E Leiserson，Ronald L Rivest，et al.算法導(dǎo)論［M］.潘金貴，顧鐵成，李成法，等，譯.北京：機(jī)械工業(yè)出版社，2006. Thomas H Cormen，Charles E Leiserson，Ronald L Rivest，et al.Intruduction to Algorithms［M］.Translated by PAN Jingui，GU Tie-cheng，LI Cheng-fa，et al.Beijing：China Machine Press，2006.（in Chinese）

［2］嚴(yán)蔚敏，李冬梅，吳偉民.數(shù)據(jù)結(jié)構(gòu)［M］.北京：人民郵電出版社，2011. YAN Wei-min，LI Dong-mei，WU Wei-min.Data Structure［M］.Beijing：People′s Posts and Telecommunications Press，2011.（in Chinese）

［3］王莉.常用內(nèi)部算法的比較與選擇［J］.軟件導(dǎo)刊，2006（1）：45-46. WANG Li.Comparison and Selection of Common Internal Algorithm［J］.Software Guide，2006（1）：45-46.（in Chinese）

［4］李愛(ài)華，劉曉紅，張衍杰.基于完全二叉樹(shù)概念的算法設(shè)計(jì)與分析［J］.山東理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2006，20（3）：56-58. LIAi-hua，LIU Xiao-hong，ZHANG Yan-jie.Based on completely two forks trees conceptalgorithm design and analysis［J］.Journal of Shandong University of Technology：Science and Technology，2006，20（3）：56-58.（in Chinese）

［5］辛運(yùn)幃，劉王景，陳有祺.數(shù)據(jù)結(jié)構(gòu)與算法［M］.北京：高等教育出版社，2006. XIN Yun-wei，LIU Jing，CHEN You-qi.Data Structure and Algorithms［M］.Beijing：Higer Education Press，2006.（in Chinese）

Realization and Application of a Quick Sort Algorithm

LI Pei-nan
（Southwest China Institute of Electronic Technology，Chengdu 610036，China）

A quick sortmethod called heap sort is introduced.The principle of this method is discussed by using a simple example together with completecinary tree.The codes for the method realized by C are provided.The advantages an disadvantages are analysed in comparison with other sort methods in term of time frame and assist memory space.Experiment indicates when sorting mass data，the heap sort has better efficiency.

sort algorithm；quick sort；heap sort；time complexity；assist memory space

the B.S.degree in 1994.She is now an engineer.Her research direction is satellite-borne product design.

1001-893X（2012）02-0225-05

2011-07-29；

2011-12-27

TP31

A

10.3969／j.issn.1001-893x.2012.02.022

黎佩南（1972—），女，重慶人，1994年獲學(xué)士學(xué)位，現(xiàn)為工程師，主要研究方向星載產(chǎn)品設(shè)計(jì)。

Email：minicat234＠sohu.com

LI Pei-nan was born in Chongqing，in 1972.She