【学员专栏019期】详解常见4种排序-周子逸
作者：周子逸
ID：初雪_Matt
学校：长沙市芙蓉区育才小学， 四年级
博客地址：https://www.luogu.com.cn/blog/magic-matt/pai-xu-suan-fa-jiu-zhao-wo
排序算法
| 排序名称 | 时间复杂度 | 额外空间复杂度 |
|---|---|---|
| 冒泡排序(bubble sort) | 最差、平均都是
 ，最好是 |
|
| 插入排序(insertion sort) | 最差、平均都是
，最好是 |
|
| 归并排序(merge sort) | 最差、平均、最好都是
|
|
| 选择排序(Selection sort) |
|
|
一. 冒泡排序
1 冒泡排序流程
排序是指将一个无序序列按照某个规则进行有序排列，而冒泡排序是排序算法中最基础的一种。现给出一个序列
，其中元素的个数为
，要求将他们从小到大的顺序排序。
冒泡排序的本质就是交换，即每次通过交换的方法把当前剩余元素的最大值移动到一端，而当剩余元素减少到为0时，排序结束。为了让排序的过程更加清楚，举个例子
现在有个数组
，其中有
个元素，分别为
，
,
,
,
演示
第一轮：
| 3 | 4 | 1 | 5 | 2 | 是否交换 | |
|---|---|---|---|---|---|---|
| 第1次 | 小 | 大 | no | |||
| 第2次 | 大 | 小 | yes | |||
| 3 | 1 | 4 | 5 | 2 | ||
| 第3次 | 小 | 大 | no | |||
| 第4次 | 大 | 小 | yes | |||
| 3 | 1 | 4 | 2 | 5 |
第二轮：
5已确认位置
| 3 | 1 | 4 | 2 | 5 | 是否交换 | |
|---|---|---|---|---|---|---|
| 第1次 | 大 | 小 | yes | |||
| 1 | 3 | 4 | 2 | 5 | ||
| 第2次 | 小 | 大 | no | |||
| 第3次 | 大 | 小 | yes | |||
| 1 | 3 | 2 | 4 | 5 |
第三轮：
5,4已确认位置
| 1 | 3 | 2 | 4 | 5 | 是否交换 | |
|---|---|---|---|---|---|---|
| 第1次 | 小 | 大 | no | |||
| 第2次 | 大 | 小 | yes | |||
| 1 | 2 | 3 | 4 | 5 |
全已排好！
冒泡排序是一种稳定排序！
Q：啥是稳定排序？
A: 稳定排序是指在原数组中相等的两个元素在排完序后，其相对位置不发生改变，这种排序就被称之为稳定排序。
2 冒泡排序的实现
使用双重
循环，内层变量为
， 外层为
，在内层循环中不断的比较相邻的两个值
的大小，如果
的值大于
的值，交换两者位置，每循环一次，外层的
增加
，等到
等于
的时候，结束循环。
3 程序实现
#include<bits/stdc++.h>
using namespace std;
int n, a[10005], ans;
int main(){
cin>>n;//几个数字
for(int i=0; i<n; i++){
cin>>a[i];//读入
}
for(int i=0; i<n-1; i++){ //依次确定从n到2这些位置的数
for(int j=0; j<n-i-1; j++){ //枚举相邻两个元素
if(a[j] > a[j+1]){
swap(a[j],a[j+1]);//交换两数
ans++;
}
}
}
for(int i=1;i<=n;i++) cout<<a[i]<<' ';//输出整理后数组
return 0;
}
4 优秀好题
P1116 车厢重组(洛谷)
思路：
这道题完全是个板子题，重组时的反转
其实跟前面叙述的两数交换是一样的，完全可以用冒泡排序做，但要注意最后输出的是需要的次数，不是换完以后的数组，在循环里面弄个
就行了
:
#include<bits/stdc++.h>
using namespace std;
int n, a[10005], ans;
int main(){
cin>>n;
for(int i=0; i<n; i++){
cin>>a[i];
}
for(int i=0; i<n-1; i++){
for(int j=0; j<n-i-1; j++){
if(a[j] > a[j+1]){
swap(a[j],a[j+1]);
ans++;//每执行一次交换ans++
}
}
}
cout<<ans;//输出统计次数
return 0;//结束撒花！
}
P1716 双调序列(洛谷)
思路：
这道题十分的简单，题面已经介绍的很清楚了，至于代码编写过程，有两个坑，第一个是冒泡排序后的输出该怎么弄，其实可以用
的双变量循环，这样就可以两头同时查找并输出，注意换行，第二个坑是要判断当两个变量碰到一起的时候要输出最中间的，由于
中的除号自带整除效果，所以要将所有的
都加
再
才行。
#include<bits/stdc++.h>
using namespace std;
int n,i,j;//注意双变量需提前设置
int a[1050];//数组开大点
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=n-1;i>=1;i--){
for(int j=1;j<=i;j++){
if(a[j]<a[j+1])
swap(a[j],a[j+1]);
}
}//可爱的冒泡排序
for(i=1,j=n;i<j;i++,j--)//双变量循环格式需牢记
cout<<a[i]<<endl<<a[j]<<endl;
if(i==j)//特判遇到一起的情况
cout<<a[(n+1)/2];
return 0;
}
AT953 マッサージチェア(洛谷)
思路：
这道题比上一道题难一些，但还是板子，一共六个数，分为学生和座椅，不能混合在一起，需要
个数组，数组不用开太大，因为只有
个数，将两个数组都冒泡排序一下，再设置一个
，循环三次
就行了（岛国题要换行！）
#include <bits/stdc++.h>
using namespace std;
int a[5],b[5],temp,ans=0;
int main(){
for(int i=1;i<=3;i++){
cin>>a[i];
}
for(int i=1;i<=3;i++){
cin>>b[i];
}
for(int i=1;i<3;i++){
for(int j=i+1;j<=3;j++){
if(a[i]>a[j]){
swap(a[i],a[j]);
}
}
}
for(int i=1;i<3;i++){
for(int j=i+1;j<=3;j++){
if(b[i]>b[j]){
swap(b[i],b[j]);
}
}
}
for(int i=1;i<=3;i++){
ans=ans+abs(a[i]-b[i]);
}
cout<<ans<<endl;//注意换行
return 0;
}
中间有行代码很奇怪，你可能会问倒数第5行不是
吗，加个
干嘛，其实要考虑
比
大的情况，那
岂不是成了负数，为了防止这个情况，要加个绝对值
P1012 [NOIP1998 提高组] 拼数
思路：
这道题是冒泡的变形，没什么好讲的，很简单
code：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
string a[25];
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=n;i>=1;i--){
for(int j=1;j<=i;j++){
if(a[j]+a[j+1]<a[j+1]+a[j]) swap(a[j],a[j+1]);
}
}
for(int i=1;i<=n;i++){
cout<<a[i];
}
return 0;
}
二. 选择排序
1 选择排序流程
选择排序也是最简单的排序算法之一，如下图所示，选择排序是指，对一个序列
中的元素
到
,令
从1到
枚举，每趟从待排序部分
中选择最小的元素，令其与待排序部分的第一个元素
进行交换，这样元素
就会与当前有序区间
形成新的有序区间
,在
趟操作后，所有元素才是有序的。
2 选择排序实现
依次从
到
个位置，用
来枚举，每一次通过找最值将第一小（或第i大）的数放入第二个位置，再用个
来枚举
到
的区间，如果
的话，
,由于
不能改变，要提前把一个变量
，然后循环完后进行两数交换。
3 程序实现
#include<bits/stdc++.h>
using namespace std;
int n, a[10005], ans;
int main(){
cin>>n;//几个数字
for(int i=0; i<n; i++){
cin>>a[i];//读入
}
for(int i = 1;i<=n-1;i++){//枚举1到n-1
int pos=i;//提前赋值
for(int j=i+1;j<n;j++){//枚举i+1到n的区间
if(a[j]<a[pos]) pos=j;//相当于i=j
}
swap(a[i],a[pos]);//交换最终两数
}
for(int i=1;i<=n;i++) cout<<a[i]<<' ';//输出整理后数组
return 0;
}
4 优秀好题
AT1313 カードと兄妹
思路：
输入数组后将对它排序，直接用选择排序模板先排好序，注意下标从
开始，再用个
循环统计奇数还是偶数大，每次循环弄个
即可，最后输出
就好了。
#include <bits/stdc++.h>
using namespace std;
int n, num[1010];
int ans;
int main() {
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> num[i];
}//输入不多说
for(int i;i<=n-1;i++){
int pos=i;
for(int j=i+1;j<n;j++){
if(num[j]<num[pos]) pos=j;
}
swap(num[i],num[pos]);
}//选择排序模板
for (int i = n - 1; i >= 0; i -= 2) {
ans += num[i];
}//统计ans
cout << ans << endl;
return 0;
}
三. 插入排序
1 插入排序流程
插入排序的过程就像插牌一样，要有顺序的将扑克牌插好，插入排序便是如此，每次确定一个元素，枚举到比它大的时候，将它插到那个大的前面去，下面用个例子来解释。
假设现在
,共
个元素，则
次操作
通过上面例子，你应该对直接插入排序的过程有了个清晰的了解。可以看到，插入排序是将待插入元素一个个插入到初始有序部分，插入的位置遵循了使插入后依然有序的原则，一般都是从后往前枚举有序部分来进行插入的
2 插入排序实现
放到代码的注释里了！
3 插入排序代码
下面就不给千篇一律的主函数代码了
void insertSort(){
for(int i=2;i<=n;i++){//从2到n枚举起，因为第一个一定有序
int val=a[i];//存当前的数
int j=i-1;//定义j，注意因为是倒着的所以是i-1
while(j>=1&&a[j]>val){//判断是否满足插入条件
a[j+1]=a[j];//如果满足即插入
j--;//再减1循环
}
a[j+1]=val;//注意存当前插入过的位置
}
return ;//void函数，不需要返回值
}
4 优秀好题
插入排序与冒泡和选择是一样的，题目都可以做，在这里就不讲了。
这里指给大家留下一道我自己创造的一个练习题，欢迎来看练习题(https://www.luogu.com.cn/problem/U160403)
四. 归并排序
1 归并排序流程
归并排序是基于“归并”这个思想的排序方法，它的排序原理是：将序列两两分组,将序列归并为
个组，组内单独排序；然后再将这些组两两归并，生成
个组，组内再单独排序，依次类推，直到只剩下一个组为止，时间复杂度为
。
同样，我们再来看一个例子，要将序列{66,12,33,57,64,27,18}进行归并排序。
① 第一趟，两两分组，得到四组：{66,12}，{33,57}，{64,27}，{18}，组内单独排序得到新序列：
② 第二趟，将四个组继续并起来，得到两组：
，组内单独排序，得到新序列
③ 第三趟，将两个组继续并起来，得到了一组{12,33,57,66,18,27,64}，组内单独排序，得到新序列{12,18,27,33,57,64,66}。算法结束
整个过程如下图4-1一样!
2 插入排序实现
放到代码的注释里了！
3 程序实现
这个算法用递归比较简单，只需要反复将当前区域[left,right]分成两半，然后将该区域进行搜索，最后进行合并与排序
code：
#include <bits/stdc++.h>
using namespace std;
int a[100005],tmp[100005],n;
void mergesort(int lt,int rt){
if(lt==rt) return ;
int mid=(lt+rt)/2;
mergesort(lt,mid);//排左半边
mergesort(mid+1,rt);//排右半边
int i=lt,j=mid+1,p=lt;
while(i<=mid&&j<=rt){
if(a[i]<a[j]) tmp[p++]=a[i++];
else tmp[p++]=a[j++];
}
while(i<=mid)//如果左半边还有数
tmp[p++]=a[i++];
while(j<=rt)//如果右半边还有数
tmp[p++]=a[j++];
for(int k=lt;k<=rt;k++) a[k]=tmp[k];
return ;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
mergesort(1,n);//排序边界
for(int i=1;i<=n;i++){
cout<<a[i]<<' ';
}
return 0;
}
4 优秀好题
因为归并排序代码繁多，不如其它三种排序，me还没有找到合适的题目，只要不卡时间尽量不用它，前面的都可以用它来做，只不过模板会改很多而已。