基數排序法

在CSDN中看到有個題目說要排列0~100000中n個數，時間複雜度為O(n)。嗯，回覆是說用線性時間排序之類的，像基數排序法，所以去研究一下基數排序法，也練習了一下：

#include <iostream>
#include <algorithm>

using namespace std;

void radixsort(int* data)
{
    int temp[10][10] = { 0 };
    int order[10] = { 0 };
    int n = 1;

    while (n <= 1000)   // 看有幾位數就增加
    {
        // 分配數字到那個桶子內
        for (int i = 0; i < 10; ++i)
        {
            int key = (data[i] / n) % 10;
            temp[key][order[key]] = data[i];
            ++order[key];
        }

        // 重新組合data
        int k = 0;
        for (int i = 0; i < 10; ++i)
        {
            if (order[i] != 0)  // 表示桶子有東西
            {
                for (int j = 0; j < order[i]; ++j, ++k)
                    data[k] = temp[i][j];
            }
            order[i] = 0;
        }
        n *= 10;
    }
}

void show(int num)
{
    cout << num << " ";
}

int main()
{
    int data[10] = { 20, 354, 69, 55, 64, 157, 1236, 87, 96, 455};
    radixsort(data);
    for_each(&data[0], &data[9], show);
    return 0;
}

也順利練習一下STL的for_each。