基数排序（radix sort）

真言

宿舍很冷，但是为了将来，什么苦都得忍着，忍方可成大事。

主题

给一堆相同具有相同位数的数排序。这些数有一个共同的特点具有相同的位数。

思路

举个例子呗，例子最好理解了。

比如有如下数据，{329,457,657,839,436,720,355}.这些数字都是三位的，也就是具有相同的位数。

我们知道，对于一位数字只能是从0~9里的一个，一共有十种可能，对于单位的数字我们可以用长度为十的哈希表（开放地址的链表）去存储数据，这样我们的数据就可以存起来了。

算法演示过程

时间复杂度（n*m），n为数据量，m为数字的位数。

实验

程序结果截图

代码(只供参考)

代码一年前写的，很水。。。
data.txt

329/457/657/839/436/720/355/

test.cpp

#include 
     
      
#include 
      
        #include 
       
         using namespace std ; int const size = 7; int const bit = 3 ; class radix_sort { int * Aint ; public: // function:构造函数; radix_sort(void); // function:get data from file; void dataReader(); // function:sort the data; void sort(); // function:show the data; void datashow(); // line is the line num; void tableinert(int (&T)[10][size],int line,int data); // function: save data out to file; void datasave(); // function:析构函数; ~radix_sort(void); }; // function:构造函数; radix_sort::radix_sort(void) { Aint = new int[size] ; } // function:get data from file; void radix_sort::dataReader() { ifstream fileReader ; fileReader.open("data.txt"); int i= 0 ; char c; while(i
        
         >Aint[i]>>c; i++; } cout<<"read over "<
         
          tableinert(table,mod,Aint[i]); } i = 0 ; // use time to get space; // table is saved to Aint; for( k = 0; k<10;k++) { num = 0; while(table[k][num] != -1) { Aint[i++]=table[k][num] ; table[k][num] = -1 ; num++; } } cout<<"the first time:"<
          
           datashow(); if(i!= size) { cout<<"error"<
           
            dataReader(); RS->datashow(); RS->sort(); RS->datasave(); delete RS ; system("pause"); return 0; }