基數排序

2017-08-28 21:27:21、

writer：pprp

基數排序，基于每一位進行的桶排序

實作起來很難，也很巧妙

代碼及講解如下：

/*
@theme: 基數排序
@writer:pprp
@start: 21:00
@end: 21:25
@declare:優化加強版的桶排序
@date:2017/8/28
*/

#include <bits/stdc++.h>
#define maxn 10    //整形排序
#define maxSize 10     //關鍵字個數，這裡為整形位數
#define N 100

using namespace std;

int NumInPos(int num,int pos)
{
    int temp = 1;
    for (int i = 0; i < pos - 1; i++)
        temp *= 10;

    return (num / temp) % 10;
}


//data需要排序的數組，Size是數組個數
void RadixSort(int* data, int Size)
{
    int *Radix[maxn];    //分别為0~9的序列空間
    for (int i = 0; i < 10; i++)
    {
        Radix[i] = (int *)malloc(sizeof(int) * (Size + 1));
        Radix[i][0] = 0;    //index為0處記錄這組資料的個數
    }
    
    //枚舉當按照哪一位進行桶排序
    for (int pos = 1; pos <= maxSize; pos++)    //從個位開始到31位
    {
          //将所有的元素按照第POS位進行排序
        for (int i = 0; i < Size; i++)    //配置設定過程
        {
            int num = NumInPos(data[i], pos);  //第pos位的值為num
            int index = ++Radix[num][0]; //相當于一個計數器
            Radix[num][index] = data[i]; //将該位置的記錄中記載下來該元素的值
        }
            //雙指針 i是用來指向radix數組，進行周遊
            //       k是用來周遊i指向部分的元素
            //       j是用來指向數組data的指針，進行++
        for (int i = 0, j =0; i < maxn; i++)    //收集0- 9
        {
            for (int k = 1; k <= Radix[i][0]; k++)
                data[j++] = Radix[i][k];
            Radix[i][0] = 0;    //複位
        }
    }
}



int main()
{
      int a[N];
      for(int i = 0 ;i < 15 ; i ++)
      {
//          srand((int)time(NULL)+i);
            a[i] = rand()%1000;
            cout << a[i] <<" ";
      }
      cout << endl;     
      
      RadixSort(a,15);
      
      for(int i= 0 ; i < 15; i++)
      {
            cout << a[i] << " ";
      }
      cout << endl;
      
      
      return 0;
}      

代碼改變世界