桶排序和计数排序(非比较排序算法)

桶排序

桶排序是一种基于分配的排序算法，特别适合用来排序均匀分布的数据。它的基本思想是将输入的数据分到有限数量的桶里，然后对每个桶内的数据分别进行排序，最后再将各个桶内的数据合并得到最终的排序结果。(通常用于浮点数，因为浮点数是有范围的比如说0.2在0和1之间，1.4在1和2之间)

计入我们要给一串数组排序，我们用桶排序应该怎么排序呢？
在这里插入图片描述

桶排序的步骤：

1.创建桶：根据输入数据的范围，创建若干个桶。

2.数据分配：遍历输入数组，将每个元素放入相应的桶中。

3.桶内排序：对每个非空桶进行排序。可以使用其他的排序算法，如插入排序或快速排序。

4.合并结果：将所有非空桶中的数据按顺序合并起来，形成排序后的数组。

桶排序的时间复杂度：

平均时间复杂度：O(n + k)，其中n是待排序元素的数量，k是桶的数量。通常情况下，k 与 n 是线性相关的，所以时间复杂度接近 O(n)。
最坏时间复杂度：O(n²)，当所有元素都被分配到同一个桶时，桶内排序可能退化到 O(n²)。
空间复杂度：O(n + k)。

我们来看一道例题

洛谷P1271

代码如下：

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

// 定义桶的数量
const int BUCKET_COUNT = 100; // 假设使用 100 个桶

int main() {
    int n, m;
    // 从标准输入读取两个整数 n 和 m
    cin >> n >> m;

    // 创建一个二维向量，每个向量代表一个桶
    vector<vector<int>> buckets(BUCKET_COUNT);

    // 遍历 m 次，从标准输入读取每一个整数 x
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        // 将 x 放入对应的桶中
        // 使用简单的比例公式计算 x 应该属于哪个桶
        int bucketIndex = (x * BUCKET_COUNT) / (n + 1); // 分桶逻辑
        buckets[bucketIndex].push_back(x);
    }

    // 对每个桶内的数据进行排序
    for (int i = 0; i < BUCKET_COUNT; i++) {
        sort(buckets[i].begin(), buckets[i].end());
    }

    // 合并所有桶，并输出排序后的结果
    for (int i = 0; i < BUCKET_COUNT; i++) {
        for (int j = 0; j < buckets[i].size(); j++) {
            cout << buckets[i][j] << ' ';
        }
    }
    return 0;
}

计数排序

计数排序（Counting Sort）是一种线性时间复杂度的排序算法是一种特殊的桶排序，适用于整数排序。它的基本思想是：通过统计每个元素出现的次数，进而直接确定它们在排序数组中的位置。

在这里插入图片描述

计数排序的特点：

适用于已知范围且数据分布相对集中的整数排序。
时间复杂度为 O(n + k)，其中 n 是待排序的元素个数，k 是元素的最大值与最小值之间的差值。
计数排序是稳定排序，即相同元素在排序后仍保持其相对顺序。
计数排序适合于当排序的元素范围较小时使用，当数据范围很大时会消耗较多的空间。

计数排序的步骤：

1.找到数组中的最大值和最小值，确定数据范围。

2.创建一个计数数组，记录每个元素出现的次数。

3.根据计数数组中的累积和，确定每个元素在排序数组中的位置。

4.根据计数数组，将输入数组中的元素按序填入输出数组。

还是刚刚的那道题洛谷P1271

代码如下：

#include <iostream>
using namespace std;

// 定义一个常量 N，表示数组的大小
const int N = 2e6 + 10;
// 声明一个大小为 N 的整型数组 a
int a[N];

int main()
{
    int n, m;
    // 从标准输入读取两个整数 n 和 m
    cin >> n >> m;

    // 遍历 m 次，从标准输入读取每一个整数 x
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        // 增加数组 a[x] 的计数
        a[x]++;
    }

    // 遍历 0 到 n 的所有整数
    for (int i = 0; i <= n; i++)
    {
        // 对于数组 a[i] 中的每一个计数，输出整数 i
        for (int j = 1; j <= a[i]; j++)
        {
            cout << i << ' ';
        }
    }

    return 0;
}