关于排序
zhuyucheng6046 · · 算法·理论
众所周知，排序在一些算法中出现，甚至直接影响代码的时间，今天我们来看看几种常见的排序。
时间复杂度为 O(n+m) 的算法。
1. 计数排序（不常用）：
通过“票箱”排序，如下列代码(就是将对应数放进对应数组内，数组就是“票箱”）：
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
cin>>n>>m;//n表示选票的个数，m表示候选人的个数
int a[n+1]={};
for(int i=1;i<=n;i++)
{
int tmp;
cin>>tmp;
a[tmp]++;
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=a[i];j++)
{
cout<<j<<" ";
}
}
return 0;
}在这里数组是“票箱”，每读入一个数对应的票箱就加一，然后按照数量输出。
这个排序的方法适合在数据较小时使用，时间复杂度为：
适合题目类型：
数据较小时可用，虽然时间复杂度还可以。
相对题目：
P1271 选举学生会
时间复杂度为 O(n^{2}) 的算法（一般来说不常用，容易 TLE）。
2. 选择排序：
如图：
选择排序思路
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
稳定性：
举个例子，序列
排序代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n+1];
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(a[j]<a[i]) swap(a[i],a[j]);
}
}
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}每次交换后都会一部分有已经排序，不需要再改变，时间复杂度：
适合： 数据较小题目，否则容易爆时间复杂度。
不适合题目（会TLE）：
P1177 【模板】排序
参考文献：
选择排序(计算机、数学术语) - 百度百科
3. 冒泡排序
如图：
算法剖析：
假定序列中有
实现方法：
（1）第
（2）第
（3）重复以上过程，共需经过
对于序列（
(1) 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
(2) 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
(3) 针对所有的元素重复以上的步骤，除了最后一个。
(4) 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
算法分析:
冒泡排序总的平均时间复杂度为
算法稳定性：
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
排序代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n+1];
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++)
{
for(int j=1;j<=n-i;j++)
{
if(a[j]>a[j+1]) swap(a[j],a[j+1]);
}
}
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}时间复杂度
适合： 数据较小题目，否则容易爆时间复杂度。
不适合题目（会TLE）：
P1177 【模板】排序
参考文献：
冒泡排序（计算机科学领域的排序算法）_百度百科
4. 插入排序：
如图：
算法介绍：
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上只需用到
插入排序的时间复杂度：
最好情况：当输入数组已经是有序的时候，插入排序只需要进行
最坏情况：当输入数组是逆序的时候，需要进行
插入排序的稳定性：
插入排序是稳定的排序算法。如果待排序的序列中存在两个或两个以上具有相同关键字的记录，由于相等元素在排序前后位置不变，所以记录的相对次序保持不变，因此插入排序是稳定的。
插入排序的应用场景：
插入排序适用于数据量较小且部分有序的数据集。对于大规模数据集，插入排序的效率较低。通常在数据规模大于
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n+10];
for(int i=0;i<n;i++) cin>>a[i];
for(int i=1;i<n;i++)
{
int now=a[i],j=0;
for(int j=i-1;j>=0;j--)
{
if(a[j]>now) {
a[j+1]=a[j];
a[j]=now;
}
else break;
}
}
for(int i=0;i<n;i++) cout<<a[i]<<" ";
return 0;
}适合： 数据较小题目，否则容易爆时间复杂度。
不适合题目（会TLE）：
P1177 【模板】排序
关于插入排序参考文献：
插入排序_百度百科
插入排序 - TianJiankun - 博客园
时间复杂度为 O(n\log n) 的算法（基本什么排序都适合）。
5. 快速排序：
结合选择排序和插入排序的优点。
代码：
#include<bits/stdc++.h>
using namespace std;
void _sort(int a[],int l, int r)
{
int i=l,j=r,flag=a[(l+r)/2],tmp;
do{
while(a[i]<flag) i++;
while(a[j]>flag) j--;
if(i<=j){
swap(a[i],a[j]);
i++;j--;
}
}while(i<=j);
if(l<j) _sort(a,l,j);
if(i<r) _sort(a,i,r);
}
int main()
{
int n;
cin>>n;
int a[n+10];
for(int i=1;i<=n;i++) cin>>a[i];
_sort(a,1,n);
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}适合题目：
P1177 【模板】排序
sort 函数与快速排序不同之处
相信很多人都会说：“与这个快排代码性质相同的函数叫：
其实，他们并不一样：
实现方式
快速排序：基于分治思想，选择一个基准元素（也叫哨兵数），将数组分割成两个子数组，左边的子数组所有元素小于基准值，右边的子数组所有元素大于基准值，然后递归地对这两个子数组进行排序。