珂朵莉Chtholly
Lv.1
ZJ蒟蒻，在线求饶
获赞:0收藏:0浏览:0作品收藏:0
签名:IOI AK me
Lv.1
ZJ蒟蒻，在线求饶
签名:IOI AK me
在 大家喜欢用什么排序算法啊 中回复
值域不大的话珂以用桶排，复杂度O(n)
桶排的实质是出现次数的映射。
for(int i=1;i<=n;i++){cin>>x;mp[x]++;}
如果值域较大，那么有几种 O(n log n) 的做法。堆排序珂以用STL优先队列priority_queue简单的实现；快速排序用STL中的sort()函数会非常方便，完全不复杂……考场上是一行代码吧
sort(a,a+n);
至于优先队列实现堆排序：
priority_queue<int> q;//定义一个int型优先队列
q.push(x);//插入x，自动排序
q.pop();//弹出堆顶（删除最大元素）
q.top();//获取最大元素因为堆是完全二叉树，那么 O(n log n)，和快排是一样的。
归并排序实现复杂，但是可以求逆序对。
其实用BST或者平衡树也是可以实现的，中序遍历就是有序了。只是很复杂。可以看看这篇帖子https://shequ.cod喵/community/340952
或者看看爵士的博客。
2020-11-28T20:29:13 点赞:0