大神的世界

假設有n個數要排序該怎麼做呢?

這裡要介紹的排序法叫做「radix sort」

radix sort 中文翻作 基底排序法

方法: 按照每一位數的大小做排序

         位數有小到大討論

ex:     1   21  6  3  81  543  62  13  做排序

首先，我們先找出最大值，也就是543

543告述我們，數列中的最大位數為3 (3位數)

接著，我們由個位數開始做排序，直到百位數

個位數排序

1  21  81  62  3  543  13  6

十位數排序(沒該位數，則視為0)

1  3  6  13  21  62  81  543

百位數做排序

1  3  6  13  21  62  81  543

完成

穩定性: 穩定

程式碼:

#include <cstdio>
#include <queue>

using namespace std;

void radixSort();

int input[100];
int inputSize;

int main()
{

    scanf("%d", &inputSize);
    for(int i = 0; i<inputSize; i++)
        scanf("%d", &input[i]);

    radixSort();

    for(int i = 0; i<inputSize; i++)
        printf("%d ", input[i]);
    printf("\n");

    return 0;
}

void radixSort()
{
    int i, j, k;

    //find max number
    int max_num = 0;
    for(i = 0; i<inputSize; i++)
        if(input[i] > max_num)
            max_num = input[i];

    //bucketSort
    queue<int> buckets[10];

    j = 1;
    while(max_num/j){
        for(i = 0; i<inputSize; i++)
            buckets[ (input[i]/j) %10].push(input[i]);

        k = 0;
        for(i = 0; i<10; i++)
            while(!buckets[i].empty()){
                input[k++] = buckets[i].front();
                buckets[i].pop();
            }

        j*=10;
    }
}