排序的定义

这个不用说吧
就是根据某个条件对一个数列进行有序的操作
例如要求从小到大排序、从大到小排序等等

排序的分类

比较排序$(Comparison$ $Sorts)$

特点：通过元素间的比较决定顺序
时间复杂度下限：$O(n$ $log$ $n)$

排序算法	平均时间复杂度	空间复杂度	稳定性	特点
冒泡排序	$O(n^2)$	$O(1)$	稳定	简单但慢
选择排序	$O(n^2)$	$O(1)$	不稳定	每次选最小放前面
插入排序	$O(n^2)$	$O(1)$	稳定	对小规模数据高效
快速排序	$O(n$ $log$ $n)$	$O(logn)$	不稳定	分治思想，实际最快
归并排序	$O(n$ $log$ $n)$	$O(n)$	稳定	分治+合并，需额外空间
堆排序	$O(n$ $log$ $n)$	$O(1)$	不稳定	利用堆结构

非比较排序$(Non-Comparison$ $Sorts)$

特点：不直接比较元素，利用数值特性
时间复杂度：可突破$O(n$ $log$ $n)$下限

排序算法	时间复杂度	空间复杂度	稳定性	适用场景
计数排序	$O(n+k)$	$O(k)$	稳定	整数且范围小（$k$为范围）
桶排序	$O(n+k)$	$O(n+k)$	稳定	数据均匀分布
基数排序	$O(d(n+k))$	$O(n+k)$	稳定	整数按位排序（$d$为位数）

建议

• 通用：快速排序（STL 的 sort）
• 稳定：归并排序（STL 的 stable_sort）
• 小范围整数：计数排序
• 数据大：堆排序（避免快排递归栈溢出）

注：实际代码实现需根据数据特点选择

模板代码示例

这里给出常用的冒泡排序、选择排序、快速排序等
内容解释在代码注释里，全是干货可以直接食用

冒泡排序

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    //核心代码
    for(int i=1;i<=n-1;i++){//n-1轮排序
        bool swapped=false;//优化：记录是否发生交换
        for(int j=1;j<=n-i;j++){//每轮比较前n-i个元素
            if(a[j]>a[j+1]){//相邻元素比较
                swap(a[j],a[j+1]);//交换
                swapped=true;
            }
        }
        if(!swapped)break;//本轮无交换说明已有序
    }
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    //排序后结果
    return 0;
}

选择排序

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    //核心代码
    for(int i=1;i<=n-1;i++){//n-1轮选择
        int minn=i;//记录最小值位置
        for(int j=i+1;j<=n;j++){//在未排序部分找最小值
            if(a[j]<a[minn])minn=j;
        }
        swap(a[i],a[minn]);//把最小值放到已排序末尾
    }
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    //排序后结果
    return 0;
}

快速排序

可以用自己写函数更改排序条件
一般配合结构体使用，下篇文章有讲到

#include<iostream>
#include<algorithm>
//sort函数必要头文件，如果不想加可以自己写sort
using namespace std;
int a[5000001];//待排序数组
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);//直接调用sort函数排序[1,n]区间
	for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    //排序后结果，快排是最简单的排序~
	return 0;
}

插入排序

#include<iostream>
using namespace std;
int a[5000001];//待排序数组
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=2;i<=n;i++){//从第二个元素开始!!
        int key=a[i];//当前要插入的元素
        int j=i-1;
        while(j>=1&&a[j]>key){//向前找插入位置
            a[j+1]=a[j];//元素后移
            j--;
        }
        a[j+1]=key;//插入元素
    }
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    //排序后结果
    return 0;
}

计数排序

#include<iostream>
using namespace std;
const int N=5000001;
const int K=100000;//数据范围自行调整
int a[N],cnt[K],b[N];
void csort(int n){
	for(int i=1;i<=n;i++)cnt[a[i]]++;
	for(int i=1;i<K;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--)b[cnt[a[i]]--]=a[i];
	for(int i=1;i<=n;i++)a[i]=b[i];
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	csort(n);
	for(int i=1;i<=n;i++)cout<<a[i]<<" ";
	return 0;
}

这个注释不好写，讲一下

变量定义说明：

• a[]：待排序数组
• cnt[]：计数数组
• b[]：临时存储排序结果
• K：数据最大值范围

流程：

• 统计每个元素出现次数（cnt[a[i]]++）
• 计算前缀和确定元素位置（cnt[i]+=cnt[i-1]）
• 反向填充保证稳定性（b[cnt[a[i]]--]=a[i]）
• 回写到原数组（a[i]=b[i]）

注意事项：

• 仅适用于非负整数排序
• 数据范围K需要提前确定
• 时间复杂度：O(n+K)（线性时间）

例题实战

$【题目传送门】$

P1177 【模板】排序

题目描述

将读入的 $N$ 个数从小到大排序后输出。

输入格式

第一行为一个正整数 $N$。

第二行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数。

输出格式

将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入输出样例 #1

输入 #1

5
4 2 4 5 1

输出 #1

1 2 4 4 5

说明/提示

对于 $20\%$ 的数据，有 $1\le N\le 10^3$；

对于 $100\%$ 的数据，有 $1\le N\le 10^5$，$1\le a_i\le 10^9$。

分析

简单的排序模板题，范围不大
可以直接用最简单的$sort$秒过
没看懂的可以看上方代码↑有注释解释
直接上代码↓

例题代码

#include <iostream>
#include <algorithm>
using namespace std;
int n,a[1000005];//数组范围10^5
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);//快排
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    return 0;
}

题单推荐

$排序\cdot 题单$
例题和题单来自$洛谷$

~ $完结撒花$ ~

附：这篇比较简单，之前忘记讲了
之前漏了很多，把基础补回来之后再讲后面的例题
下一篇预告：递推递归或者结构体