用c++完成本题目：考虑这样一种计数排序：对每个待排记录，扫描整个序列统计比它小的记录个数 $c$， 则 $c$ 就是他在序列中的正确位置。值得注意的是，计数排序只适用于不存在重复记录的情 况。编程实现这种算法，并分析其时间代价，与直接选择排序进行比较

以下是 C++ 代码实现：

#include <iostream>
#include <vector>
using namespace std;

void countingSort(vector<int>& arr) {
    int n = arr.size();
    vector<int> cnt(n, 0);
    for (int i = 0; i < n; i++) {
        int c = 0;
        for (int j = 0; j < n; j++) {
            if (arr[j] < arr[i]) c++;
        }
        cnt[c] = arr[i];
    }
    for (int i = 0; i < n; i++) {
        arr[i] = cnt[i];
    }
}

int main() {
    vector<int> arr = {5, 3, 1, 4, 2};
    countingSort(arr);
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

时间代价分析：

- 外循环需要遍历 $n$ 个元素。
- 内循环需要统计比当前元素小的元素个数，这需要遍历 $n$ 个元素，故内循环的时间复杂度为 $O(n)$。
- 将当前元素放到计数数组中正确的位置，这需要 $O(1)$ 的时间。
- 最后需要再遍历一次计数数组，将元素放回原数组中，这也需要 $O(n)$ 的时间。

因此，总的时间复杂度为 $O(n^2)$。

与直接选择排序进行比较：

- 直接选择排序的时间复杂度为 $O(n^2)$，与计数排序相同。
- 直接选择排序需要进行多次交换操作，而计数排序只需要将元素放到计数数组中，故计数排序的常数因子比直接选择排序小，实际运行速度更快。
- 计数排序只适用于不存在重复记录的情况，而直接选择排序没有这个限制。