基数排序

基数排序分为从低位到高位，和从高位到低位两种。

一、从低位到高位

采用计数排序才完成每一趟的排序，每一趟计数排序都是对带排序数组某一位的排序。

void RadixSort(int* array, int length)
{
    int* auxiliary_array = new int[length];//for placing sorted digits
    int* digit_array = new int[length];//record the certain digit of the number in array

    for (int digit = 1; true; ++digit) {
        int count = 0;//count the certain digit of the array[index], if the number is positive
        for (int index = 0; index < length; ++index) {
            digit_array[index] = static_cast<int>(array[index] / pow(10, digit - 1))
                        - static_cast<int>(array[index] / pow(10, digit)) * 10;//get the certain digit of array[index]
                        
            if (digit_array[index] > 0) {
                ++count;
            } else {
                digit_array[index] = 0;
            }
        }

        if (count <= 0) break;

        int counting_array[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};//fpr counting the total number of the digits
        for (int index = 0; index < length; ++index) {
            ++counting_array[ digit_array[index] ];
        }

        for (int index = 1; index < 10; ++index) {
            counting_array[index] += counting_array[index - 1];
        }

        for (int index = length - 1; index >= 0; --index) {
            auxiliary_array[ counting_array[ digit_array[index] ] - 1 ] = array[index];
            --counting_array[ digit_array[index] ];
        }

        for (int index = 0; index < length; ++index) {
            array[index] = auxiliary_array[index];
        }
    }

    delete[] auxiliary_array;
    delete[] digit_array;
}