如何使用C++中的计数排序算法

如何使用C++中的计数排序算法

计数排序算法是一种比较简单且高效的排序算法，适用于对整数序列进行排序的场景。它的基本思想是确定每个元素前面有多少个元素比它小，从而确定它在有序数组中的位置。

计数排序算法的步骤如下：

1. 找出待排序数组中的最大值，以确定计数数组的长度。
2. 创建一个长度为最大值加一的计数数组，并初始化为0。
3. 遍历待排序数组，统计每个元素的出现次数，并将统计结果保存到计数数组中。
4. 对计数数组进行变形，使得每个位置的值等于它前面位置值之和。
5. 创建一个与待排序数组等长的临时数组，用于保存排序结果。
6. 从后向前遍历待排序数组，根据计数数组确定每个元素在排序结果中的位置，并将元素存储到临时数组中。
7. 将临时数组的结果复制回待排序数组，完成排序。

下面是一个使用C++语言实现的计数排序算法的示例代码：

立即学习“C++免费学习笔记（深入）”；

Bolt.new

Bolt.new是一个免费的AI全栈开发工具

下载

#include <iostream>
#include <vector>

using namespace std;

void countingSort(vector<int>& arr) {
    int max_val = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }

    vector<int> count(max_val + 1, 0);

    for (int i = 0; i < arr.size(); i++) {
        count[arr[i]]++;
    }

    for (int i = 1; i < count.size(); i++) {
        count[i] += count[i - 1];
    }

    vector<int> temp(arr.size());
    for (int i = arr.size() - 1; i >= 0; i--) {
        temp[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    for (int i = 0; i < arr.size(); i++) {
        arr[i] = temp[i];
    }
}

int main() {
    vector<int> arr = {5, 1, 4, 3, 2};
    countingSort(arr);

    cout << "排序后的数组：";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

以上代码中，我们使用了一个辅助的计数数组来统计每个元素的出现次数，然后通过变形计算每个元素在排序结果中的位置。最后，我们将排序结果复制回原数组。

通过以上示例代码，我们可以看到计数排序算法的实现过程，它的时间复杂度为O(n+k)，其中n为待排序序列的长度，k为最大元素值与最小元素值之差加一。

总结起来，计数排序算法是一种简单但高效的排序算法，适用于对整数序列进行排序的场景。通过使用适当的数据结构和算法，我们可以更好地完成排序任务。