基数排序（radix sort）

真言

科技是第一生产力。

引言

快过年了，祝大家新年快乐，在过年期间，博客也会一直出新。

思路

radix sort很牛叉，以空间换时间 时间复杂度O（n） 空间复杂度O（max+n）max为要排序的数据中的最大值。 举个例子说明思路吧，感觉很牛叉，一会你看程序结果就知道了，比那比较排序快多了。 源数据，如下
利用辅助空间数组，记录每个元素的个数
利用元素的个数统计出每个元素在排好序的数据中的位置。
预处理以后如下
源数据每个元素从后往前处理，把其放在应该放的位置。 1
2
3
4

5
6
7
8
ok，over.

实验

给1000,000个数据排序耗时如下

代码

test.cpp

#include 
     
      
#include 
      
        #include 
       
         using namespace std ; // radix sort int * Radix_sort(int *data,const int length); int const size = 1000000 ; int main( ) { DWORD s,e; int * data = new int[size]; int * result; for(int i = 0; i
        
          0) { int Max = data[0]; for(int i = 0;i
         
          Max) Max = data[i]; int * Hash = new int[Max+1]; int * result = new int[length]; for(int i=0; i <= Max; i++) { Hash[i] = 0; } for(int i=0;i < length;i++) { Hash[data[i]]++; } for(int i = 0; i < Max; i++) { Hash[i+1] = Hash[i] + Hash[i+1]; } for(int i = length-1;i >= 0;i--) { result[ Hash[ data[i] ] -1] = data[i] ; Hash[ data[i] ] = Hash[ data[i] ] - 1 ; } return result ; } else { cout<<"exception of input Radix sort"<