猫史档案馆

珂朵莉Chtholly

值域不大的话珂以用桶排，复杂度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

或者看看爵士的博客。

点赞0

无情的AC自动鸡

泻药，无特殊要求直接用STL的std::sort()和std::reverse()是最方便的。

点赞0

爵士OIer

泻药，猴子排序

点赞0

86135clc

猴子排序

点赞0