Day-14 线性时间演算法 : Radix sort

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, 图片源於维基百科