0.简介
本帖将简要介绍简单且常用的排序与类搞笑排序。
1.什么是排序？
排序大家都不陌生，我们平时玩扑克牌都要用排序得嘞[doge]
那么到底什么是排序？
排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。 分内部排序和外部排序，若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
2.桶排序
桶排序是我们学习到的第一种排序，他的排序方法就像是用桶来排序一样，所以被称为“桶排序”。
2.1 桶排序的原理
桶排序（Bucket sort）的工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。
例如说，我们对序列“4 3 3 1 2”进行排序，我们可以假定有四个桶。
第一个桶：
第二个桶：
第三个桶：
第四个桶：
接下来，我们从第一个元素开始，“4”应当放在第四个桶里。
第一个桶：
第二个桶：
第三个桶：
第四个桶：4
接下来，后两个元素“3 3”应当放在第三个桶里。
第一个桶：
第二个桶：
第三个桶：3 3
第四个桶：4
下一个元素“1”应该放在第一个桶里。
第一个桶：1
第二个桶：
第三个桶：3 3
第四个桶：4
当然，最后一个元素“2”就是第二个桶里。
第一个桶：1
第二个桶：2
第三个桶：3 3
第四个桶：4
如果我们从小到大排序，那我们就从第一个桶里，将元素全部输出。输出元素序列应当是“1 2 3 3 4”，与我们的排序序列相同。
2.2 桶排序的代码写法
我们发现，桶排序内桶及其重要，所以我们可以用一个数组来模拟桶的过程。
我们定义一个数组 a。
接着，输入所有元素后，从第一个元素开始，我们用a[i]来表示第i个桶装了多少个元素的话，那明显我们应该让a[元素]++。
接下来，我们从第一个桶开始，有多少个元素就输出多少个，就可以成功排序。
代码：
#include <bits/stdc++.h>
using namespace std;
int a[105];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
a[x]++;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=a[i];j++){
cout<<i<<" ";
}
}
return 0;
}
大家可以自行理解，第一个for循环指的是输入元素与将元素装进桶中，第二个for循环嵌套指的是输出元素。
2.3 例题练习
2.3.1 CSP2020-J-2 直播获奖
虽然这是一道CSP-J的水题，但是这是一道简单的桶排序题目，难度为橙标。
题目描述
NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 w\% ，即当前排名前 w\% 的选手的最低成绩就是即时的分数线。
更具体地，若当前已评出了 p 个选手的成绩，则当前计划获奖人数为 \max(1, \lfloor p \times w \%\rfloor) ，其中 w 是获奖百分比， \lfloor x \rfloor 表示对 x 向下取整， \max(x,y) 表示 x 和 y 中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。
作为评测组的技术人员，请你帮 CCF 写一个直播程序。
输入格式
第一行有两个整数 n, w 。分别代表选手总数与获奖率。
第二行有 n 个整数，依次代表逐一评出的选手成绩。
输出格式
只有一行，包含 n 个非负整数，依次代表选手成绩逐一评出后，即时的获奖分数线。相邻两个整数间用一个空格分隔。
样例 #1
样例输入 #1
10 60
200 300 400 500 600 600 0 300 200 100
样例输出 #1
200 300 400 400 400 500 400 400 300 300
样例 #2
样例输入 #2
10 30
100 100 600 100 100 100 100 100 100 100
样例输出 #2
100 100 600 600 600 600 100 100 100 100
提示
样例 1 解释
数据规模与约定
各测试点的 n 如下表：
| 测试点编号 | n= |
|---|---|
| 1 \sim 3 | 10 |
| 4 \sim 6 | 500 |
| 7 \sim 10 | 2000 |
| 11 \sim 17 | 10^4 |
| 18 \sim 20 | 10^5 |
对于所有测试点，每个选手的成绩均为不超过 600 的非负整数，获奖百分比 w 是一个正整数且 1 \le w \le 99 。
提示
在计算计划获奖人数时，如用浮点类型的变量（如 C/C++ 中的 float 、 double，Pascal 中的 real 、 double 、 extended 等）存储获奖比例 w\% ，则计算 5 \times 60\% 时的结果可能为 3.000001 ，也可能为 2.999999 ，向下取整后的结果不确定。因此，建议仅使用整型变量，以计算出准确值。
——————————————————————————————————————————————
本题目按照题意模拟即可。主要原因是我们发现每个选手成绩不超过 600 ，CCF给的是一个多么完美的水！我们只需要用桶排序，用桶存储每个分数的人数。当然，其实这里不需要用到桶排序，只需要借助思想而已，连“排序”这一步都省去了。
对于每一个选手，计算出当前的获奖人数并从高到低枚举分数，当当前获奖人数 \ge k 时输出当前分数即可。
代码：不放
3.sort函数排序
对于这个函数，同学们可真是好用犇犇感激连连，不做过多介绍，只介绍他的用法了。
3.1 int/long long 型排序
3.1.1 升序排序
sort排序如果不做任何函数，那就会对数组进行升序排序。如果数组下标为 1 \sim n ，则升序排序的代码为 sort(a+1,a+n+1)。
3.1.2 降序排序
sort排序由于内定为升序排序，所以需要用 greater<>() 函数来放在sort函数的结尾。
例如：
sort(a+1,a+n+1,greater<int>());
小Tips：在<>的里面填写的是数组的类型，常见的为 int 与 long long。
3.1.3 升序、降序排序的代码
升序排序：
#include <bits/stdc++.h>
using namespace std;
int a[10005];
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
}
降序排序：
#include <bits/stdc++.h>
using namespace std;
int a[10005];
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1,greater<int>());
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
}
只要熟知这两个代码，常规排序题都可以斩于马下啦！
3.1.4 不普通的排序
有一些排序并不常规，例如这道 IOI 的水犇犇。
P9114 [IOI2009] POI - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
参考我的AC代码，如果遮住排序部分就会发现，这不同于升序排序与降序排序，是一种全新排序方法。
#include <bits/stdc++.h>
using namespace std;
int a[2005][2005]; //a[i][j] = 第 i 个选手的第 j 题得分情况
int c[2005];// 每个选手共做对几题
int p[2005];// 第 i 题的分值
struct node{
int cnt,b,i;
}q[2005];
int main(){
int n,t,z;
cin>>n>>t>>z;
for(int i=1;i<=n;i++){
for(int j=1;j<=t;j++){
cin>>a[i][j];
if(a[i][j]==1){
c[i]++;
}
}
}
for(int i=1;i<=t;i++){
int sum=0;// 本题没做对的人数
for(int j=1;j<=n;j++){
if(a[j][i]==0){
sum++;
}
}
p[i]=sum;
}
for(int i=1;i<=n;i++){
int sum=0;// 这个人的分数
for(int j=1;j<=t;j++){
if(a[i][j]==1){
sum+=p[j];
}
}
q[i].cnt=sum;
q[i].b=c[i];
q[i].i=i;
}
cout<<q[z].cnt<<" ";
sort(q+1,q+n+1);//这里是错误的
for(int i=1;i<=n;i++){
if(q[i].i==z){
cout<<i;
return 0;
}
}
}
这时，my_cmp自定义函数闪亮登场！！！
我们定义一个与题意相符的函数，随后就像降序排序那样，写到sort函数后就ok啦！
int my_cmp(node x,node y){
if(x.cnt!=y.cnt){
return x.cnt>y.cnt;
}else if(x.b!=y.b){
return x.b>y.b;
}else{
return x.i<y.i;
}
}
恭喜你，学会了 I AK IOI T1!
3.2 其余类型的排序
对于其余类型，我们仍然使用 my_cmp 来计算。例如 char 类型，就是一种完美适用于 my_cmp 的排序类型。
4.冒泡排序
冒泡排序是一种复杂度较高的排序，不过新手会很多使用。
4.1 冒泡排序的原理
通过不断地交换数从而将序列变为正的。在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。 如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。
经过 i 次扫描后，数列的末尾 i 项必然是最大的 i 项，因此冒泡排序最多需要扫描 n-1 遍数组就能完成排序。因此，冒泡排序的时间复杂度为 O(n^2) 。
当然，另一个以交换为根本的排序为 【选择排序】。
4.2 冒泡排序的代码写法
冒泡排序还是很简单实现的。
4.3 例题练习
4.3.1 【模版】排序
详见洛谷 P1177。
大家可以在洛谷题目内编写冒泡排序代码，进行提交检验自己的排序。
5. 选择排序
选择排序即 Selection sort，若以数组实现则选择排序是不稳定的。
5.1 选择排序的原理
在 【冒泡排序】 内我们说过，选择排序也是一个以交换为本的排序算法。 它的工作原理是每次找出第 i 小的元素，然后将这个元素与数组第 i 个位置上的元素交换。
5.2 选择排序的代码实现
以交换为本，定义一个数来模拟下标即可。
for(int i=1;i<n;i++){
t=i;
for(int j=i+1;j<=n;j++){
if(a[j]<a[t]){
t=j;
}
}
swap(a[i],a[t]); // 通过上方类似于打擂台的方法，我们找到了最小的数，进行交换
}
看完代码，我们可以看出本代码与冒泡排序代码类似，时间复杂度为 O(n^2) 。
6.插入排序
6.1 插入排序的原理
插入排序（英语：Insertion sort）是一种简单直观的排序算法。它的工作原理为将待排列元素划分为「已排序」和「未排序」两部分，每次从「未排序的」元素中选择一个插入到「已排序的」元素中的正确位置。
类似于自己在抽到一些牌后按顺序排序牌，这是相同的原理。
6.2 插入排序的代码实现
如下：
记得CCF有道题叫插入排序
6.3 插入排序例题
6.3.1 【排序】插入排序的过程
题目描述：
给出 n 数序列 A ，求出 A 序列排序成 B 序列的插入排序过程。
例如 A={2,3,1,4,5} ，则插入排序的过程为：
- 拿出数 2 移到 B 序列
- 拿出数 3 移到 B 序列
- 拿出数 1 移到 B 序列
- 拿出数 4 移到 B 序列
- 拿出数 5 移到 B 序列
对于 100\% 的数据， 1 \le n \le 1000,1 \le A_i \le 2 \times 10^4 。
代码：
由题意模拟，定义两个数组 A 与 B 。接着进行双重循环，每次循环从 A 数组内拿出 A_i ，再来一重循环找到 B 数组内可以插入 A_i 的位置。代码就不放了（懒得写）。
7.快速排序
快速排序即 Quicksort ，又称分区交换排序。
7.1 快速排序的原理
快速排序的工作原理是通过 分治 的方式来将一个数组排序。
快速排序分为三个过程：
- 将数列划分为两部分（要求保证相对大小关系）；
- 递归到两个子序列中分别进行快速排序；
- 不用合并，因为此时数列已经完全有序。
和 【归并排序】 不同的是，第一步并不是直接分成前后两个序列，而是在分的过程中要保证大小关系。为了保证平均时间复杂度，一般是随机选择一个数 k 来当做两个子数列的分界。（归并排序见后）
7.2 快速排序的代码实现
void QuickSort(int* a, int left, int right){
if(left>=right){
return;
}
int begin=left,end=right;
int povit=begin;
int key=a[begin];
while(begin<end){
while(end>=begin&&a[end]>=key){
end--;
}
//右边的放到左边坑，因此右边有坑了
a[povit]=a[end];
povit=end;
//从左边找比key大的值放到右边坑里
while(begin<end&&a[begin]<=key){
begin++;
}
//左边的放到右边坑里，坑更新到左边
a[povit]=a[begin];
povit=begin;
}
//将基准值放到两指针交界处
a[begin]=key;
QuickSort(a,left,povit-1);
QuickSort(a,povit+1,right);
}
这是以递归方式实现的一种快速排序。