radix sort(Herman Hollerith)

基數排序(radix sort)是種應用在打孔卡排序機上面的演算法，每一張卡片有80列，在每一列上機器可以選12個孔(如圖所示)中任一一個孔進行打孔。然後根據打孔的位置將他們分別放到12個容器中。工程師就可以一個接一個容器去蒐集卡片，第一個位置打孔的卡片在最上面，依序排列。

對於10進位的數字來說，每一列只會用到10個數字。一個d位數就會用到d列。卡片排序機一次只能查看一列，所以需要對n張卡片上的d位數進行排序，我們就需要設計一個排序演算法。

Example:

1. 先比較最低位數，由小到大進行排列，接著一路比較到最高位數(LSB形式)

 1.      2.        3.        4.
329     72 0     7 2 0     3 29
457     35 5     3 2 9     3 55
657     43 6     4 3 6     4 36
839 --> 45 7 --> 8 3 9 --> 4 57
436     65 7     3 5 5     6 57
720     32 9     4 5 7     7 20
355     83 9     6 5 7     8 39

radix sort是按照最低有效位數來解決卡片的排序問題。

1. 329放到9號容器, 457放到7號容器, 657放到7號容器...接著從0號容器開始蒐集卡片，0號卡片在上，依序排放，得到2.的結果。
2. 720放到2號容器, 355放到5號容器...，開始蒐集，並依序排放，得到3.結果。
3. 720放到7號容器, 329放到3號容器...，開始蒐集，並依序排放，得到4.結果。

為了保證radix sort的正確性，卡片排序機所執行的排序必須是穩定的，也就是確保在取出卡片時能夠保持原本的順序。

正確性(使用歸納法)

假設一組序列第t - 1位已經完成排序，我們想要對第t位進行排序。對第t位來排序有兩種狀況:

1. 如果這兩個元素是相同的，也就是有兩個元素在第t位有相同的數字，則他們排序的順序會由第t - 1位來決定，第t - 1位是完成排序的，因此第i位也會是排序的，且是穩定的，因為他們的相對位置在上一步，也就是在針對第t - 1位時沒有變化。
2. 如果這兩個元素是不相同的，則按照第t - 1位的排序方法他們就會是有序的。

從這個證明可以發現到，排序本身必須要具有穩定性。

radix sort效率

我們必須要對某一位數進行排序，對於個別位數的排序，如果使用的排序演算法，由於我們要進行很多輪，因此最後的結果會比來得糟糕。這裡使用counting sort來對個別位數進行排序。

我們已知counting sort的時間複雜度為，但我們並不會將每個位元切分之後獨立進行排序，輸入的值不一定會是整數，有可能是二進位數，甚至是字串等等，我們可以將好幾個位元當作一個位數進行處理。

在一般情況下，如果我們給定n個d位數，其中每一個位數有k個可能的數值，如果每一位排序使用counting sort，則可以在的時間內完成排序。

假設我們給定n個二進位數，每一個數長達位元，則我們輸入的數的範圍為到之間。

如果將每個數，以位元作為一個位數，則整個數會有位數，在這樣得情況下，我們只需要進行輪比較，也就是我們以進制的方式來表示一個數，每一位數最大值為，最小值為，可以將counting sort中的視為。

在這樣的情況下，每一輪排序所需要的時間為，我們需要的執行的總時間為，整個想法為透過來減少比較的次數，藉此來降低執行時間。對於我們希望越大越好，藉此降低比較的次數，但是也不能太大，因為我們使用counting sort，數字越大效率越差，且太大時，將主導整個函數的增長，因此希望比較小。

如果我們希望能夠選到最大的，同時希望不要大過於，也就是，我們可以取，因為，如果我們選取，我們就能夠得到這個演算法的執行時間的上界，將代入，得到的時間複雜度為。

隨著增長到大於後，的增長速度會比來的快，因此，當時，時間複雜度為。

如果減小到以下，則項會越來越大，而項會保持。當時，時間複雜度為，漸進情況是最好的。

radix sort實作

將n個d位的元素放到A陣列中

RADIX-SORT(A,d)
    for i = 1 to d
        use a stable sort to sort array A on digit i

這裡穩定的排序法使用counting sort

首先，先找到輸入序列中的最大值，假定輸入皆為10進位數，則radix為10，有10個容器，透過radix來取個位，十位，百位。

using namespace std;
int max_number(int *, int);
void radix_sort(int *, int);
int *counting_sort(int *, int, int);
int main(void)
{
    int array[6] = {2341, 4653, 456, 321, 567, 2187};
    for (auto i : array)
    {
        cout << i << ' ';
    }
    cout << '\n';
    radix_sort(array, 6);
    for (auto i : array)
    {
        cout << i << ' ';
    }
}

int max_number(int *A, int a_length)
{
    int max = A[0];
    for (int i = 1; i < a_length; i++)
    {
        if (A[i] > max)
        {
            max = A[i];
        }
    }
    return max;
}

void radix_sort(int *A, int a_length)
{
    int max = max_number(A, a_length);
    for (int radix = 1; max / radix > 0; radix *= 10)
    {
        counting_sort(A, a_length, radix);
    }
}

int *counting_sort(int *A, int a_length, int radix)
{
    int *output_array = (int *)malloc(sizeof(int) * a_length);
    int count[10];

    for (int i = 0; i < 10; i++)
    {
        count[i] = 0;
    }
    for (int i = 0; i < a_length; i++)
    {
        count[(A[i] / radix) % 10]++; //依照尾數放入容器中
    }
    for (int i = 1; i < 10; i++)
    {
        count[i] = count[i] + count[i - 1];
    }
    for (int i = a_length - 1; i >= 0; i--)
    {
        output_array[count[(A[i] / radix) % 10] - 1] = A[i];
        count[(A[i] / radix) % 10]--;
    }
    for (int i = 0; i < a_length; i++)
    {
        A[i] = output_array[i];
    }
}

參考資料:Introduction to algorithms 3rd, 圖片源於維基百科