快捷導(dǎo)航

C++實現(xiàn)基數(shù)排序的方法詳解

更新時間：2013年05月29日 11:48:06 作者：

本篇文章是對使用C++實現(xiàn)基數(shù)排序的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

基數(shù)排序(Radix sort)是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)?；鶖?shù)排序的發(fā)明可以追溯到1887年赫爾曼·何樂禮在打孔卡片制表機(jī)(Tabulation Machine)上的貢獻(xiàn)。
它是這樣實現(xiàn)的： 將所有待比較數(shù)值(正整數(shù))統(tǒng)一為同樣的數(shù)位長度,數(shù)位較短的數(shù)前面補(bǔ)零. 然后, 從最低位開始, 依次進(jìn)行一次排序.這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個有序序列.
基數(shù)排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。
（以上轉(zhuǎn)自維基百科）
下面是我自己的實現(xiàn)，不足之處，還望指正：

復(fù)制代碼代碼如下:

// RadixSort.cpp : 定義控制臺應(yīng)用程序的入口點。
#include "stdafx.h"
#include <iostream>
using namespace std;
//定義隊列的節(jié)點
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;
  }
 }
 //在隊列的尾部添加一個元素，節(jié)點不存在，需要程序創(chuàng)建
 void push(int e)
 {
  Node* p = new Node;
  p->data = e;
  p->next = NULL;
  rear->next = p;
  rear = p;
 }
 //在隊列的尾部添加一個節(jié)點，節(jié)點原來就存在
 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);   //單個數(shù)據(jù)元素具有的位數(shù)
  int d;      //用來存儲待比較的數(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;
 }
 //判斷隊列是否為空
 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;
  }
 }

 //基數(shù)排序
 void RadixSort(Queue& que)
 {
  //定義一個指針數(shù)組，數(shù)組中存放十個分別指向十個隊列的指針
  Queue* arr[10];
  for (int i = 0; i < 10; i++)
  {
   arr[i] = new Queue;
  }
  int d = 1;
  int m = que.lenData(); //取得待排序數(shù)據(jù)元素中的最大位數(shù)

  //將初始隊列中的元素分配到十個隊列中
  for(int i = 0; i < m; i++)
  {
   Node* p = que.front->next;
   Node* q;
   int k;  //余數(shù)為k，則存儲在arr[k]指向的隊列中
   while (p != NULL)
   {
    k = (p->data/d)%10;
    q = p->next;
    arr[k]->push(p);
    p = q;
   }
   que.clear(); //清空原始隊列

   //將十個隊列中的數(shù)據(jù)收集到原始隊列中
   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;
}

下面的代碼轉(zhuǎn)自維基百科，還沒仔細(xì)分析，先拿過來

復(fù)制代碼代碼如下:

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