C++完成基數排序的辦法詳解。本站提示廣大學習愛好者：（C++完成基數排序的辦法詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是C++完成基數排序的辦法詳解正文
基數排序(Radix sort)是一種非比擬型整數排序算法，其道理是將整數按位數切割成分歧的數字，然後按每一個位數分離比擬。因為整數也能夠表達字符串（好比名字或日期）和特定格局的浮點數，所以基數排序也不是只能應用於整數。基數排序的創造可以追溯到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;
}
