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

黎佩南（中國西南電子技術研究所，成都610036）

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

黎佩南
（中國西南電子技術研究所，成都610036）

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

排序算法；快速排序；堆排序；時間復雜度；輔助存儲空間

1 引言

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

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

2 排序算法簡介

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

2.1 插入排序

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

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

2.2 交換排序

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

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

快速排序是對起泡排序的一種改進，通過一次排序?qū)⒂涗浄指畛瑟毩⒌膬刹糠?，其中一部分的關鍵字均比另一部分小，再分別對這兩部分記錄進行排序，達到整個序列有序。

2.3 選擇排序

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

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

堆排序是一種基于完全二叉樹對葉子節(jié)點進行不斷篩選的排序過程。

2.4 歸并排序

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

2.5 基數(shù)排序

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

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

3 堆排序算法

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

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

堆的定義如下：n個元素的序列｛k1，k2，k3，…，kn｝，當且僅當滿足下列關系時，稱之為堆［4］。

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

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

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

3.1 推出堆頂及篩選

下面以圖2所示堆為例來說明這一過程。

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

3.2 建堆

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

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

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

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

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

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

4 代碼實現(xiàn)

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

4.1 篩選

代碼如下：

void Sift（int iRootIndex，int iNodeCount）

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

｛

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

bool bFinish=false；／／排序完成標志

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

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

／／獲取當前根節(jié)點值

iTemp=DataList［iRootIndex］；

iRoot=DataList［iRootIndex］；

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

iLeftLeave=iRootIndex；

iRightLeave=2*iLeftLeave；

／／重新排列堆

while（iRightLeave＜=iNodeCount＆＆！bFinish）

｛

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

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

iRightLeave=iRightLeave+1；

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

if（iTemp＜=DataList［iRightLeave］）

bFinish=true；

else

｛

iLeftLeave=iRightLeave；

iRightLeave=2*iLeftLeave；

｝

｝

／／根節(jié)點插入恰當位置

DataList［iLeftLeave］=iRoot；

｝

4.2 堆排序

代碼如下：

void HeapSortAsdc（void）

｛

／／對DataList中的數(shù)據(jù)從第n／2個記錄開始進行篩選建堆

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

Sift（i，iCount-1）；

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

｛

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

Exchange（DataList，0，i）；

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

Sift（0，i-1）；

｝

｝

說明：

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

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

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

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

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

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

5 算法比較與分析

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

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

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

［1］Thomas H Cormen，Charles E Leiserson，Ronald L Rivest，et al.算法導論［M］.潘金貴，顧鐵成，李成法，等，譯.北京：機械工業(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］嚴蔚敏，李冬梅，吳偉民.數(shù)據(jù)結構［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］.軟件導刊，2006（1）：45-46. WANG Li.Comparison and Selection of Common Internal Algorithm［J］.Software Guide，2006（1）：45-46.（in Chinese）

［4］李愛華，劉曉紅，張衍杰.基于完全二叉樹概念的算法設計與分析［J］.山東理工大學學報（自然科學版），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］辛運幃，劉王景，陳有祺.數(shù)據(jù)結構與算法［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年獲學士學位，現(xiàn)為工程師，主要研究方向星載產(chǎn)品設計。

Email：minicat234＠sohu.com

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