C++计数排序详解

什么是计数排序?

计数排序是一种非比较型排序算法，它的基本思想是统计所有元素的出现次数，然后根据每个元素的出现次数，依次将这些元素放入数组中，从而得到排好序的数组。

计数排序的基本原理

计数排序利用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素个数。然后根据数组C来将A中的元素排到正确的位置。例如，如果C[3]=4，那么值等于3的元素就该排在第5个位置，因为之前有4个元素小于它。

计数排序的实现步骤

void countSort(int arr[], int n) {
    int maxElement = *max_element(arr, arr + n);  // 找出待排序数组中的最大值
    int count[maxElement + 1]{0};                  // 创建count数组, 初始化元素都为0
    int sortedArray[n];                            // 创建排序后的数组sortedArray

    // 计算待排序数组中每个元素出现的个数，并记录在count数组中
    for(int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // 计算每个元素在排序后的数组中应该出现的位置
    for(int i = 1; i <= maxElement; i++) {
        count[i] += count[i - 1];
    }

    // 将待排序数组中的元素按照count数组中的计数放入排序后的数组sortedArray中
    for(int i = 0; i < n; i++) {
        sortedArray[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // 将排序后的数组拷贝回原数组
    copy(sortedArray, sortedArray + n, arr);
}

计数排序的示例

示例一

假设有一个待排序数组arr[] = {5, 6, 2, 3, 8, 6, 9, 1, 3}，则计数排序的执行过程如下：

1. 找出待排序数组中的最大值，为9，创建count数组，共有10个元素，全部初始化为0。
2. 将待排序数组中每个元素出现的个数计算出来，并记录在count数组中，结果如下：

	0	1	2	3	4	5	6	7	8	9
count数组中的元素个数	0	1	1	2	0	1	2	0	1	1

1. 计算每个元素在排序后的数组中应该出现的位置，并记录在count数组中，现在count数组中的元素值为：

	0	1	2	3	4	5	6	7	8	9
count数组中的元素个数	0	1	2	4	4	5	7	7	8	9

1. 将待排序数组中的元素按照count数组中的计数，放入排序后的数组sortedArray中，现在sortedArray数组中的元素值为：

位置	0	1	2	3	4	5	6	7	8
元素	1	2	3	3	5	6	6	8	9

1. 将排序后的数组拷贝回原数组arr[]中，得到的排序结果为：arr[] = {1, 2, 3, 3, 5, 6, 6, 8, 9}.

示例二

假设有一个待排序数组arr[] = {3, 4, 5, 2, 6, 3, 9, 1, 10, 8}，则计数排序的执行过程如下：

1. 找出待排序数组中的最大值，为10，创建count数组，共有11个元素，全部初始化为0。
2. 将待排序数组中每个元素出现的个数计算出来，并记录在count数组中，结果如下：

	0	1	2	3	4	5	6	7	8	9	10
count数组中的元素个数	0	1	1	2	1	1	1	0	1	0	1

1. 计算每个元素在排序后的数组中应该出现的位置，并记录在count数组中，现在count数组中的元素值为：

	0	1	2	3	4	5	6	7	8	9	10
count数组中的元素个数	0	1	2	4	5	6	7	8	9	9	10

1. 将待排序数组中的元素按照count数组中的计数，放入排序后的数组sortedArray中，现在sortedArray数组中的元素值为：

位置	0	1	2	3	4	5	6	7	8	9
元素	1	2	3	3	4	5	6	8	9	10

1. 将排序后的数组拷贝回原数组arr[]中，得到的排序结果为：arr[] = {1, 2, 3, 3, 4, 5, 6, 8, 9, 10}.

总结

计数排序是一种简单而高效的排序算法，它的时间复杂度为O(n+k)，其中n为待排序数组的大小，k为待排序数组中最大值的大小。虽然计数排序的适用场景比较有限，但在一些特定的应用场景（例如待排序数组是小范围整数的情况下），计数排序能够达到很高的排序效率。