作者：周子逸
ID：初雪_Matt
学校：长沙市芙蓉区育才小学， 四年级
博客地址：https://www./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./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还没有找到合适的题目，只要不卡时间尽量不用它，前面的都可以用它来做，只不过模板会改很多而已。
|
