有一种简单的排序算法,叫做计数排序( Count sorting)。这种排序算法对一个待排序的表用数组表示进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关建码互不相同。计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个录的关键码比该记录的关键码小。假设针对某一个记录,统计出的计数值为c,那么,这个记录在新的有序表中的合适的存放位置即为c。 ①给出适用于计数排非序的教据表定义。 ②编写实现计数排序的算法。 ③对于有n个记录的表,关键码比较欠数是多少? ④与简单选择排序相比较,这种方法是否更好?为什么?

①计数排序适用于待排序表中所有记录的关键码互不相同的情况，可以用一个数组来表示待排序表，数组下标表示记录的关键码，数组值表示该关键码出现的次数。新的有序表也可以用一个数组来表示，数组下标表示原始待排序表中的记录，数组值表示该记录在有序表中的位置。

②计数排序的具体实现如下：

void countingSort(int arr[], int n) {
    // 找到最大值
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }

    // 统计每个关键码出现的次数
    int* count = new int[maxVal + 1];
    for (int i = 0; i <= maxVal; i++) {
        count[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // 统计计数数组中小于等于每个关键码的元素个数
    for (int i = 1; i <= maxVal; i++) {
        count[i] += count[i - 1];
    }

    // 将元素放入新数组中
    int* res = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        res[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // 将有序数组赋值回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = res[i];
    }

    delete[] count;
    delete[] res;
}

其中，arr是待排序的数组，n是数组的长度。算法首先找到数组中的最大值，然后创建一个大小为maxVal+1的计数数组count，用来统计每个关键码出现的次数。接着，统计计数数组中小于等于每个关键码的元素个数。最后，将待排序数组中的元素放入新数组中，并将有序数组赋值回原数组。

③计数排序中关键码比较的次数为0，因为该算法不需要进行关键码的比较。

④与简单选择排序相比较，计数排序的时间复杂度为O(n+k)，其中k为关键码的取值范围，且不需要进行关键码的比较，因此在关键码取值范围不大的情况下，计数排序比简单选择排序更快。但是，计数排序需要额外的空间来存储计数数组和新数组，因此在空间有限的情况下，简单选择排序可能更好。