排序算法是一個(gè)非常常見(jiàn)的問(wèn)題，其實(shí)它的原理是將整數(shù)按數(shù)字分割成不同的數(shù)字，本文是武林技術(shù)頻道小編詳解C++實(shí)現(xiàn)基數(shù)排序的方法，感興趣的朋友可以進(jìn)入下文了解一下！
基數(shù)排序(Radix sort)是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。基數(shù)排序的發(fā)明可以追溯到1887年赫爾曼·何樂(lè)禮在打孔卡片制表機(jī)(Tabulation Machine)上的貢獻(xiàn)。
它是這樣實(shí)現(xiàn)的： 將所有待比較數(shù)值(正整數(shù))統(tǒng)一為同樣的數(shù)位長(zhǎng)度,數(shù)位較短的數(shù)前面補(bǔ)零. 然后, 從最低位開(kāi)始, 依次進(jìn)行一次排序.這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個(gè)有序序列.
基數(shù)排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開(kāi)始，而MSD則相反，由鍵值的最左邊開(kāi)始。
（以上轉(zhuǎn)自維基百科）
下面是我自己的實(shí)現(xiàn)，不足之處，還望指正：
?
?
?
// RadixSort.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
#include "stdafx.h"
#include <iostream>
using namespace std;
//定義隊(duì)列的節(jié)點(diǎn)
struct Node
{
?int data;
?Node* next;
};
//定義程序所需的特殊隊(duì)列
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;
??}
?}
?//在隊(duì)列的尾部添加一個(gè)元素，節(jié)點(diǎn)不存在，需要程序創(chuàng)建
?void push(int e)
?{
??Node* p = new Node;
??p->data = e;
??p->next = NULL;
??rear->next = p;
??rear = p;
?}
?//在隊(duì)列的尾部添加一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)原來(lái)就存在
?void push(Node* p)
?{
??p->next = NULL;
??rear->next = p;
??rear = p;
?}
?//數(shù)據(jù)元素中最大位數(shù)
?int lenData()
?{
??int temp(0);//數(shù)據(jù)元素的最大位數(shù)
??int n(0);?? //單個(gè)數(shù)據(jù)元素具有的位數(shù)
??int d;????? //用來(lái)存儲(chǔ)待比較的數(shù)據(jù)元素
??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;
?}
?//判斷隊(duì)列是否為空
?bool empty()
?{
??if (front == rear)
??{
???return true;
??}
??return false;
?}
?//清除隊(duì)列中的元素
?void clear()
?{
??front->next = NULL;
??rear = front;
?}
?//輸出隊(duì)列中的元素
?void print(Queue& que)
?{
??Node* p = que.front->next;
??while (p != NULL)
??{
???cout << p->data << " ";
???p = p->next;
??}
?}
?//基數(shù)排序
?void RadixSort(Queue& que)
?{
??//定義一個(gè)指針數(shù)組，數(shù)組中存放十個(gè)分別指向十個(gè)隊(duì)列的指針
??Queue* arr[10];
??for (int i = 0; i < 10; i++)
??{
???arr[i] = new Queue;
??}
??int d = 1;
??int m = que.lenData(); //取得待排序數(shù)據(jù)元素中的最大位數(shù)
??//將初始隊(duì)列中的元素分配到十個(gè)隊(duì)列中
??for(int i = 0; i < m; i++)
??{
???Node* p = que.front->next;
???Node* q;
???int k;? //余數(shù)為k，則存儲(chǔ)在arr[k]指向的隊(duì)列中
???while (p != NULL)
???{
????k = (p->data/d)%10;
????q = p->next;
????arr[k]->push(p);
????p = q;
???}
???que.clear(); //清空原始隊(duì)列
???//將十個(gè)隊(duì)列中的數(shù)據(jù)收集到原始隊(duì)列中
???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++)//清空十個(gè)隊(duì)列
???{
????arr[i]->clear();
???}
???d *= 10;
??}
??print(que); //輸出隊(duì)列中排好序的元素
?}
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;
}
下面的代碼轉(zhuǎn)自維基百科，還沒(méi)仔細(xì)分析，先拿過(guò)來(lái)
?
?
?
#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++實(shí)現(xiàn)基數(shù)排序的方法介紹，今天武林技術(shù)頻道小編就為大家分享到這里了，希望想學(xué)習(xí)的朋友通過(guò)上面的介紹有幫助！
