基數排序算法的鏈表實現

摘 要:比較關鍵字和移動記錄是實現算法排序的兩個基本操作。在經典排序算法中，基數排序是一種不通過比較關鍵字實現排序的方法。通過示例說明了基數排序算法的基本思想，用C程序設計語言以鏈表為存儲結構實現了基數排序算法，并分析了基數排序算法的計算復雜性。

關鍵詞:算法排序基數排序鏈表

中圖分類號:TP312文獻標識碼:A文章編號:1674-098X(2011)08(b)-0023-02

排序是計算機處理數據序列最常用的一種操作。排序操作將一組無序的數據序列按某種次序重新排列，從而得到一組有序的數據序列，以方便用戶的查找，提高檢索數據的效率。下面給出排序的概念:

定義1：設有一個由個記錄 構成的有限序列，這個記錄對應的關鍵字序列為。排序就是確定的一種排列 ，使得(或 )，并通過調整中記錄的位置，得到一個新的按關鍵字非遞減(或非遞增)的有序序列的過程。

排序在處理數據序列的計算機程序中占用的時間較長，設計高效的排序算法是提高這些程序執行效率的關鍵。通常，排序算法通過兩個基本操作實現對數據序列排序:一個是通過比較關鍵字來確定數據在數據序列中的位置次序;另一個是將數據從一個位置移動到另一個位置，從而調整數據在數據序列中的位置次序。這兩個基本操作很大程度上決定排序算法的計算效率。依據算法的平均時間復雜性，將常用的排序算法分為三類:簡單排序算法，時間復雜性為，例如，直接插入排序、起泡排序、簡單選擇排序;先進排序算法，時間復雜性為，例如，希爾排序、快速排序、堆排序、歸并排序;基數排序，時間復雜性為。基數排序在關鍵字個數為一常數時，時間復雜性是線性的。基數排序是一種不通過比較關鍵字實現排序的方法，它借助多關鍵字排序的思想對單邏輯關鍵字進行排序。

算法和數據結構是計算機程序設計和軟件開發的基礎。依據“程序=算法+數據結構”的觀點，程序、算法和數據結構三者聯系密切。鏈表是一種比較簡單、實用的數據結構。排序算法采用鏈表結構實現對數據序列排序，進行插入或刪除操作，只需修改指針，可以避免移動大量記錄，從而節省時間。因此，本文首先結合實例介紹了基數排序算法的基本思想，然后采用鏈表結構通過程序的方式實現了基數排序算法，并分析了基數排序算法的計算復雜性。

1 基數排序算法的基本思想

設有一個由RADIX個單鏈表組成的鏈表集和一個由RECNUM個數據元素組成的單鏈表Head={}，每個數據元素由KEYNUM個關鍵字組成，每個關鍵字的表達式為，， 則基數排序算法的步驟如下:

1);

2)依據單鏈表Head中每個數據元素的第位關鍵字上的數字，把數據結點取下分配到RADIX個鏈表集L中，分配的原則是關鍵字的數據結點，都分配到鏈表中;

3)依次序將鏈表集， 中的全部數據結點取下收集，并鏈接這些結點構成一個新的單鏈表Head;

4)自增1，若，返回2)，否則結束。

下面通過示例進一步說明基數排序算法的基本思想。

例如，基數排序前數組a為

{278，109，63，930，589，184，505，269，8，83}

數組a中記錄的個數RECNUM=10，基數RADIX=10為十進制數，數據的最高位為百位，因此關鍵字的個數KEYNUM=3。首先，根據數組a提供的數據元素建立一個單鏈表Head={83，8，269，505，184，589，930，63，109，278}。考慮到數據元素有3個關鍵字，因此需要依次按個位、十位和百位在單鏈表Head和鏈表集L之間進行分配和收集數據結點，具體過程如下:

1)按個位數分配和收集數據結點，分配到鏈表集L中的數據結點的分布位置:L[0]={930}，L[3]={63，83}，L[4]={184}，L[5]={505}，L[8]={278，8}，L[9]={109，589，269}; 收集到單鏈表Head中的數據結點的相應位置:Head={269，589，109，8，278，505，184，83，63，930}。

2)按十位數分配和收集數據結點，分配到鏈表集L中的數據結點的分布位置:L[0]={505，8，109}，L[3]={930}，L[6]={63，269}，L[7]={278}，L[8]={83，184，589}; 收集到單鏈表Head中的數據結點的相應位置:Head={589，184，83，278，269，63，930，109，8，505}。

3)按百位數分配和收集數據結點，分配到鏈表集L中的數據結點的分布位置:L[0]={8，63，83}，L[1]={109，184}，L[2]={269，278}，L[5]={505，589}，L[9]={930}; 收集到單鏈表Head中的數據結點的相應位置:Head={930，589，505，278，269，184，109，83，63，8}。

最后，將單鏈表Head中的數據按逆序傳回給數組，得到有序數組a為{8，63，83，109，184，269，278，505，589，930}。

2 基數排序算法的鏈表實現

下面給出了基數排序算法的C語言程序代碼。程序已在VC++環境下測試通過。程序中包含下述主要模塊:創建單鏈表CreateLinkList(ArrType a)、基數排序算法的核心模塊RadixSort(ArrType a)。

#include \"stdio.h\"

#include \"math.h\"

#include \"malloc.h\"

#define RADIX 10 //基數10為十進制數

#define KEYNUM 3//記錄中關鍵字的個數

#define RECNUM 10 //記錄的個數

typedef int ArrType[RECNUM];

typedef struct LNode{//定義單鏈表結構

int data;

struct LNode *next;

}LNode，*LinkList;

typedef LNode SLList[RADIX];

LinkList CreateLinkList(ArrType a) //創建單鏈表

{int i;LinkList Head，p;

Head=(LNode *)malloc(sizeof(LNode));

Head->next=NULL;

for(i=0;i

p=(LNode *)malloc(sizeof(LNode));

p->data=a[i];

p->next=Head->next;Head->next=p;

}

return Head;

}

void RadixSort(ArrType a)

{SLList L;LinkList Head，p，q;int i，j，k;

for(i=0;i

{L[i].data=i;L[i].next=NULL;}

Head=CreateLinkList(a);//創建單鏈表Head

for(i=0;i

//分配Head中的數據結點到L中

p=Head->next;Head->next=NULL;

while(p){

q=p;p=p->next;

k=(q->data/(int)pow(RADIX，i))%RADIX;

q->next=L[k].next;L[k].next=q;

}//while

//收集L中的數據結點到Head中

for(j=0;j

p=L[j].next;L[j].next=NULL;

while(p){

q=p;p=p->next;

q->next=Head->next;

Head->next=q;

}//while

}//for

}//for

//釋放單鏈表Head，并將排序結果返回數組a

p=Head->next;free(Head);i=RECNUM-1;

while(p){q=p;p=p->next;a[i]=q->data;free(q);i--;}

}

void main()

{int i;

ArrType a={278，109，63，930，589，184，505，269，8，83};

printf(\"\The original array: \");

for(i=0;i

RadixSort(a);

printf(\"\The array has been sorted: \");

for(i=0;i

}

3 基數排序算法的計算復雜性分析

設數據序列中需要排序的記錄個數為，記錄中關鍵字的個數為，記錄中存放的是進制數。則基數排序過程中，初始化鏈表集的時間復雜性為，創建單鏈表的時間復雜性為，次分配與收集數據結點的時間復雜性為，將單鏈表中的數據結點傳回數組的時間復雜性為。因此，基數排序算法的時間復雜性為。當為一個固定常數時，基數排序算法的時間復雜性是線性的。另外，基數排序過程中額外用到數據結點，每個數據結點包含一個數據域和一個指針域，單鏈表用到一個頭結點，鏈表集用到個頭結點。因此，基數排序算法的輔助空間復雜性為。基數排序算法比較適合記錄個數較大而記錄中關鍵字的個數較小的序列。

4 結語

與其它排序算法相比，基數排序算法不通過比較關鍵字實現對序列排序，具有計算時間復雜度較低的優點。本文基數排序算法采用鏈表存儲結構實現，具有思路清晰、結構簡單、易于擴充以及容易實現等特點。將來的研究工作是在海量數據上對本文算法進一步測試，并與其它排序算法進行定量比較。另外，對本文程序的核心模塊的正確性證明也是進一步的研究工作。

參考文獻

[1]嚴蔚敏，吳偉民.數據結構(C語言版)[M].北京:清華大學出版社.1997.

[2]徐壽芳.一種新的高效基數排序算法[J].湖州職業技術學院學報.2008，(1): 17～19.

[3]何文明.一種改進后的基數排序算法[J].湘潭大學自然科學學報.2004，26(4):34～38.

[4] 盧開澄.計算機算法導引—設計與分析(第2版)[M].北京:清華大學出版社.2006.

[5]葛浩，楊傳健.基于分布計數的基數排序方法的研究[J].計算機技術與發展.2008，18(2):122～125.

[6]王向陽.任意分布數據的基數分配鏈接排序算法[J].計算機學報.2000，23(7):774～778.