willcool4ever • O(n+k)排序：计数

// 特点：只能用于非负数的排序
void countingSort(int array[], int size)
{
    // step 1:找出待排序数组中最大的值，确定数据的范围
    int max = array[0];
    for (int i= 1; i<size ; ++i) {
        if(max < array[i])
            max = array[i];
    }

    // step 2:申请数据范围大小的桶
    int *c = new int[max + 1] {0};

    for (int i=0; i<size; ++i) {
        c[array[i]]++;
    }

    // step 3:对桶计数累计
    for (int i=1; i <= max; ++i) {
          c[i] = c[i-1] + c[i];
    }

    // step 4:临时数组 r，存储排序之后的结果 int[] r
    int *r = new int[size] {0};
    for (int i=size-1; i>=0; --i) {
        int index = c[array[i]] - 1;
        r[index] = array[i];
        c[array[i]]--;
    }

    // step 5:排序后数据拷贝回原数组
    for (int i=0; i<size; ++i) {
        array[i] = r[i];
    }

    delete [] c;
    return ;
}

int main()
{
    int array[7] = {10, 122, 211, 120, 22, 23, 120};
    int size = sizeof (array) / sizeof (*array);

    printArray(array, size);

    countingSort(array, size);

    printArray(array, size);

    return 0;
}