计数排序

计数排序

/**
 *@param array is the array to sort
 *@param length is the length of the array
 *@param range is the range of the whole numbers in array
 */
void CountingSort(int* array, int length, int range)
{//this algorithm needs two auxiliary, one for counting the total number of the digits, one for placing sorted digits
    int* auxiliary_array = new int[length];//for placing sorted digits
    int* counting_array = new int[range];//fpr counting the total number of the digits

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

    for (int index = 0; index < range; ++index) {
        counting_array[index] = 0;
    }

    //the next three loops is called counting sort
    for (int index = 0; index < length; ++index) {
        ++counting_array[ array[index] ];
    }

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

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

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

    delete[] auxiliary_array;
    delete[] counting_array;
}