排序算法是一個非常常見的問題，其實它的原理是將整數按數字分割成不同的數字，本文是武林技術頻道小編詳解C++實現基數排序的方法，感興趣的朋友可以進入下文了解一下！
基數排序(Radix sort)是一種非比較型整數排序算法，其原理是將整數按位數切割成不同的數字，然后按每個位數分別比較。由于整數也可以表達字符串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用于整數?；鶖蹬判虻陌l明可以追溯到1887年赫爾曼·何樂禮在打孔卡片制表機(Tabulation Machine)上的貢獻。
它是這樣實現的： 將所有待比較數值(正整數)統一為同樣的數位長度,數位較短的數前面補零. 然后, 從最低位開始, 依次進行一次排序.這樣從最低位排序一直到最高位排序完成以后, 數列就變成一個有序序列.
基數排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。
（以上轉自維基百科）
下面是我自己的實現，不足之處，還望指正：
?
?
?
// RadixSort.cpp : 定義控制臺應用程序的入口點。
#include "stdafx.h"
#include <iostream>
using namespace std;
//定義隊列的節點
struct Node
{
?int data;
?Node* next;
};
//定義程序所需的特殊隊列
class Queue
{
public:
?Queue()
?{
??Node* p = new Node;
??p->data = NULL;
??p->next = NULL;
??front = p;
??rear = p;
?}
?~Queue()
?{
??Node* p = front;
??Node* q;
??while (p)
??{
???q = p;
???p = p->next;
???delete q;
??}
?}
?//在隊列的尾部添加一個元素，節點不存在，需要程序創建
?void push(int e)
?{
??Node* p = new Node;
??p->data = e;
??p->next = NULL;
??rear->next = p;
??rear = p;
?}
?//在隊列的尾部添加一個節點，節點原來就存在
?void push(Node* p)
?{
??p->next = NULL;
??rear->next = p;
??rear = p;
?}
?//數據元素中最大位數
?int lenData()
?{
??int temp(0);//數據元素的最大位數
??int n(0);?? //單個數據元素具有的位數
??int d;????? //用來存儲待比較的數據元素
??Node* p = front->next;
??while (p != NULL)
??{
???d = p->data;
???while (d > 0)
???{
????d /= 10;
????n++;
???}
???p = p->next;
???if (temp < n)
???{
????temp = n;
???}
???n = 0;
??}
??return temp;
?}
?//判斷隊列是否為空
?bool empty()
?{
??if (front == rear)
??{
???return true;
??}
??return false;
?}
?//清除隊列中的元素
?void clear()
?{
??front->next = NULL;
??rear = front;
?}
?//輸出隊列中的元素
?void print(Queue& que)
?{
??Node* p = que.front->next;
??while (p != NULL)
??{
???cout << p->data << " ";
???p = p->next;
??}
?}
?//基數排序
?void RadixSort(Queue& que)
?{
??//定義一個指針數組，數組中存放十個分別指向十個隊列的指針
??Queue* arr[10];
??for (int i = 0; i < 10; i++)
??{
???arr[i] = new Queue;
??}
??int d = 1;
??int m = que.lenData(); //取得待排序數據元素中的最大位數
??//將初始隊列中的元素分配到十個隊列中
??for(int i = 0; i < m; i++)
??{
???Node* p = que.front->next;
???Node* q;
???int k;? //余數為k，則存儲在arr[k]指向的隊列中
???while (p != NULL)
???{
????k = (p->data/d)%10;
????q = p->next;
????arr[k]->push(p);
????p = q;
???}
???que.clear(); //清空原始隊列
???//將十個隊列中的數據收集到原始隊列中
???for (int i = 0; i < 10; i++)
???{
????if (!arr[i]->empty())
????{
?????Node* p = arr[i]->front->next;
?????Node* q;
?????while (p != NULL)
?????{
??????q = p->next;
??????que.push(p);
??????p = q;
?????}
????}
???}
???for (int i = 0; i < 10; i++)//清空十個隊列
???{
????arr[i]->clear();
???}
???d *= 10;
??}
??print(que); //輸出隊列中排好序的元素
?}
private:
?Node* front;
?Node* rear;
};
int _tmain(int argc, _TCHAR* argv[])
{
?Queue oldque;
?int i;
?cout << "Please input the integer numbers you want to sort.Input ctrl+z to the end:" << endl;
?while (cin >> i)
?{
??oldque.push(i);
?}
?oldque.RadixSort(oldque);
??? cout << endl;
?return 0;
}
下面的代碼轉自維基百科，還沒仔細分析，先拿過來
?
?
?
#include <iostream>
using namespace std;
const int base=10;
struct wx
{
??????? int num;
??????? wx *next;
??????? wx()
??????? {
??????????????? next=NULL;
??????? }
};
wx *headn,*curn,*box[base],*curbox[base];
void basesort(int t)
{
??????? int i,k=1,r,bn;
??????? for(i=1;i<=t;i++)
??????? {
??????????????? k*=base;
??????? }
??????? r=k*base;
??????? for(i=0;i<base;i++)
??????? {
??????????????? curbox[i]=box[i];
??????? }
??????? for(curn=headn->next;curn!=NULL;curn=curn->next)
??????? {
??????????????? bn=(curn->num%r)/k;
??????????????? curbox[bn]->next=curn;
??????????????? curbox[bn]=curbox[bn]->next;
??????? }
??????? curn=headn;
??????? for(i=0;i<base;i++)
??????? {
??????????????? if(curbox[i]!=box[i])
??????????????? {
??????????????????????? curn->next=box[i]->next;
??????????????????????? curn=curbox[i];
??????????????? }
??????? }
??????? curn->next=NULL;
}
void printwx()
{
??????? for(curn=headn->next;curn!=NULL;curn=curn->next)
??????? {
??????????????? cout<<curn->num<<' ';
??????? }
??????? cout<<endl;
}
int main()
{
??????? int i,n,z=0,maxn=0;
??????? curn=headn=new wx;
??????? cin>>n;
??????? for(i=0;i<base;i++)
??????? {
??????????????? curbox[i]=box[i]=new wx;
??????? }
??????? for(i=1;i<=n;i++)
??????? {
??????????????? curn=curn->next=new wx;
??????????????? cin>>curn->num;
??????????????? maxn=max(maxn,curn->num);
??????? }
??????? while(maxn/base>0)
??????? {
??????????????? maxn/=base;
??????????????? z++;
??????? }
??????? for(i=0;i<=z;i++)
??????? {
??????????????? basesort(i);
??????? }
??????? printwx();
??????? return 0;
}
以上就是詳解C++實現基數排序的方法介紹，今天武林技術頻道小編就為大家分享到這里了，希望想學習的朋友通過上面的介紹有幫助！
