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;
}