优化桶排序

_Manstein_ · 2025-01-12 10:25:16 · 算法·理论

简单桶排序会受到数字大小的影响导致超时或爆空间。

但在我优化之下，桶排序的时间复杂度降到 O(n) ，

且不会因为数字太大而爆空间，

这一切都归功于map。

#include <map>

运用迭代器可以节省很多时间，且 map 的映射只要不爆 int 或 long long 就行了。

#include <iostream>
#include <map>//这个头文件必须加
#include <cmath>
#include <cstdio>
using namespace std;
void Bucket_Sort(int c[],int n) {
    map <long long, long long> mp;//map开long long 防止数据过大
    for (int i = 1; i <= n; i++){
        mp[c[i]]++;//桶排序
    }
    for (auto it = mp.begin(); it != mp.end(); it++) {//迭代器
        for (int i = 1; i <= it->second; i++)
        cout << it->first << " ";//输出
    }
}
int main()
{
    int a[100005], n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    Bucket_Sort(a, n);//排序
    //时间复杂度O(n)
    //空间复杂度O(n)
    return 0;
}