基數排序
一、基數排序是一種非比較型整數排序算法，其原理是將整數按位數切割成不同的數字，然後按每個位數分別比較。
其實現原理：將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後, 數列就變成一個有序序列。
二、具體操作：此排序的真正實現是通過隊列的裝置，先進先出的原理，通過把個位，十位，百位，等其他進制也一樣，放到不同的隊列中（俗稱桶）再按照先進先出的原理得到新的序列，在通過百位將其重新入桶回收等操作有獲取新的序列，按此以來得到最終的序列便是排序好的序列。
三、基數排序不同於其他排序，一般我們見到的排序都是通過比較得到的，快排，歸並都不例外，這個排序對於整數有特別好的效率而且也是一種穩定的排序。對於基數排序算法中要m次的n個節點來存放臨時元素所以給予鏈式隊列的基數排序，其算法復雜度為O(n)。對於順序隊列和鏈式隊列基數排序算法的時間復雜度相同也為O(2mn)。
接下來我們以十進制：
500,342,45,666,006,841,429,134,78,264為例：
第一次：
0
500
1
841
2
342
3
4
134
264
5
45
6
666
006
7
8
78
9
429
得到：500 841 342 134 264 45 666 006 78 429
第二次：
0
500
006
1
2
429
3
134
4
841
342 45
5
6
264
666
7
78
8
9
得到： 500 006 429 134 841 342 45 264 666 78
第三次：
0
006
45 78
1
134
2
264
3
342
4
429
5
500
6
666
7
8
841
9
得到：006 45 78 134 264 342 429 500 666 841
這就得到了排序。
排序段代碼：
/**
*基數排序的操作方法實現Radix_sort()
*SNode *S 用來接收tub的地址
*@param int a[] 表示接受要排序的數組
*@param int length 表示該要排序的數組的長度
*@param int d 表示進制，這裡假設是十進制
*@param int m 表示的是要比較的數的最大的位數
*@return 無
*/
void Radix_sort(DataType a[],int length ,int d,int m){
int power = 1,k;
//用來計算裝桶的次數
int count= 1;
//把d個隊列定義成動態數組
Queue *tub ;
tub = (Queue *)malloc(sizeof(Queue)*d);
//對每一個隊列進行初始化
cout<<"_____________________________________________"<>>>>第"<
插入段代碼：
/**
*隊列的插入，即桶的數據的裝桶操作
*@param Queue *Q用來接收傳進來的地址
*@param int num 表示要入桶的數
*return Queue *
*/
Queue *QueueAppend(Queue *Q,int num){
/**
*這裡我們首先得為rear ，front申請空間並初始化
*
*/
/* Queue *Q;
*判斷有無空間可申請，並是否申請成功
*if(Q != NULL){
* free(Q);
* Q =NULL;
*}
*Q = (Queue *)malloc(sizeof(Queue));
*if(Q !=NULL){
* cout<<"Q-頭節點和尾節點申請空間成功！"<rear = NULL;
*Q->front = NULL;
*/
/**
*這裡判斷R是否為空並釋放空間
*然後對其申請空間按
*/
SNode *p =NULL;
if(p != NULL){
free(p);
p =NULL;
}
p = (SNode *)malloc(sizeof(SNode));
if(p !=NULL){
cout<<"申請空間成功！"<data = num;//這裡得放其位數如個位，十位，百位
p->next = NULL;//到此已經成功的創建了一個新的節點
/**
*將新的節點插入隊列的末尾
*
*/
if(Q->rear != NULL){
Q->rear->next = p;
Q->rear = p;
}
if(Q->front == NULL){
Q->rear = p;
Q->front = p;
}
cout<<"裝桶成功！"<
回收段代碼：
/**
*鏈式隊列中的元素的刪除
*@param Queue *q 用來接收要回收的元素的地址
*@param DataType *d 用來存儲儲存收回的元素
*@return int
*/
int QueueDelete(Queue *q,DataType *d){
SNode *p;
/**
*判斷內存中是否有數據，有就輸出，沒有返回0
*
*/
if(q->front == NULL){
cout<<"此時隊列中無元素出列！"<front->data;
p = q->front;
q->front= q->front->next;
}
if(q->front == NULL){
q->rear = NULL;
}
free(p);//釋放節點內存空間
return 1;
} 全部代碼：
/**
*基數排序原理就是利用桶也就是隊列來排序的
*@author 菜鳥
*@version 2014.6.15
*/
#include
#include
#include
#define MaxSize 100
using namespace std;
typedef int DataType;
//定義節點用來做鏈式隊列
typedef struct Node{
DataType data;
struct Node *next;
}SNode;
//定義一個結構體將隊列的頭尾指針放在一起
typedef struct{
SNode *rear;
SNode *front;
}Queue;
//初始化頭節點與尾節點
void QueueInitiate(Queue *q){
q->rear = NULL;
q->front = NULL;
cout<<"成功初始化！"<rear = NULL;
*Q->front = NULL;
*/
/**
*這裡判斷R是否為空並釋放空間
*然後對其申請空間按
*/
SNode *p =NULL;
if(p != NULL){
free(p);
p =NULL;
}
p = (SNode *)malloc(sizeof(SNode));
if(p !=NULL){
cout<<"申請空間成功！"<data = num;//這裡得放其位數如個位，十位，百位
p->next = NULL;//到此已經成功的創建了一個新的節點
/**
*將新的節點插入隊列的末尾
*
*/
if(Q->rear != NULL){
Q->rear->next = p;
Q->rear = p;
}
if(Q->front == NULL){
Q->rear = p;
Q->front = p;
}
cout<<"裝桶成功！"<front == NULL){
cout<<"此時隊列中無元素出列！"<front->data;
p = q->front;
q->front= q->front->next;
}
if(q->front == NULL){
q->rear = NULL;
}
free(p);//釋放節點內存空間
return 1;
}
/**
*輸出函數
*@param int a[]用來接收數組
*@param int n 表示數組的長度
*@return 無
*/
void out_put(int a[],int n){
cout<<"_____________________________________________"<>>>第"<
