基数排序(Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation
Machine)上的贡献[1]。
它是这样实现的: 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次排序.这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.
基数排序的方式可以采用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++实现直接插入排序,折半插入排序,希尔排序,冒泡排序,简单选择排序,快速排序,堆排序,仅供参考!