编辑代码

#include <iostream>
#include <math.h>

using namespace std;

//计数排序的核心思想:
//(1) 根据待排序的数据，找出数据的范围max-min+1
//(2) 创建max-min+1个桶
//(3) 遍历待排序的数据，统计每一个和桶所对应的数据（array[k] - min）相等的数据的个数
//(4) 按照从小到大的顺序，把桶内的数据逐一相加，得到的就是每个数据在排序后在数组的最后一个位置（数据有相等的情况）
//(5) 从右向左遍历待排序数组，在桶里面查询其在排序后的数组的位置（这个位置需要-1，因为数组从0开始，计算的时候从1开始），插入临时数组对应的位置，桶内数据的在临时数组位置减小一位
//(6) 将临时数组中的数据拷贝回原数组
bool coutingSort(int array[], size_t arrLen) {
    if (arrLen < 2) {
        return true;
    }

    //Find maximum and minimal value
    int max = array[0];
    int min = array[0];

    for (size_t i = 1; i < arrLen; ++i)
    {
        if (min > array[i]) {
            min = array[i];
        }
        else if (max < array[i]) {
            max = array[i];
        }
    }

    // Create counting buckets
    int *countingBuckets = new int[max - min + 1]();

    // Count number of values in array
    for (size_t j = 0; j < arrLen; ++j)
    {
        ++countingBuckets[array[j] - min];
    }

    // Accumulate coutingBuckets to find the last ordered location of value in array
    for (size_t k = 1; k < (max - min + 1); ++k)
    {
        countingBuckets[k] += countingBuckets[k-1];
    }

    //Traverse the array in reversed order
    int *tempArray = new int[arrLen]();
    for (int l = arrLen - 1; l >= 0; --l)
    {
        tempArray[--countingBuckets[array[l] - min]] = array[l];
    }

    for (size_t m = 0; m < arrLen; ++m)
    {
        array[m] = tempArray[m];
    }

    delete [] countingBuckets;
    delete [] tempArray;
    return true;
}

/*void printArray(int array[], int arrLen) {
    for (int i = 0; i < arrLen; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}*/

int main(){
    int array0[] = {11, 9, 20, 56, 42, 3, 7,15,16};
    int arrayLen = sizeof(array0)/sizeof(int);

    //printArray(array0, arrayLen);
    coutingSort(array0, arrayLen);
    //printArray(array0, arrayLen);

    cout<<endl<<"最小值为: "<<array0[0]<<endl;
	cout<<endl<<"最大值为: "<<array0[arrayLen-1]; 
}