C++ 基础算法 - 排序算法
今天，我们要学*第二个算法,排序算法，就是将无序的一组数据按照某个标准进行有顺序的排列
一个有序的数列对于其他算法的执行是非常重要的，之后的一些算法就是以排序算法为基础写的
排序算法并不是一种算法，而是多种不同，但功能一样，都是用来排序的算法的统称，例如排序算法有** ( 即快速排序 )，冒泡排序，**排序，归并排序等各种各样的排序算法
排序算法可以分为两类
不稳定排序，例如快速排序，意思是一个数列**现了多个同样值的数，但是它们在原先的数列中的位置不相同，假设它们一个是 x，另一个是 y，且 x < y，则通过不稳定排序后，数列中相同的数虽然排列在一起，但是它们原先的先后顺序改变了，即 y > x，但这也不是一定的，它是有一定的概率的
稳定排序，例如冒泡排序，这种排序更加稳定，不会出现不稳定排序中相等的数的位置产生变化的情况，它会按照原来的顺序排列
以下的排序算法默认是按照从小到大进行排序的，如果需要从大到小排序就将比较符号反转即可( 除了非比较排序，如计数排序，在计数排序处我会教大家如何进行排序 )
冒泡排序
冒泡排序是很简单的一种排序算法，是通过按位比较进行排序的，具体方法为由 1 至 N - 1 进行比较，如果它们的关系不符合最终的顺序，就将它们交换，否则比较下一个数，当比较完成后，较大的数就像泡泡一样 " 浮 " 出来了，然后接着进行比较，直到较后整个数列都有序
算法思想
冒泡排序通过每次的循环选取出较大值并放在了较后面，通过 N 次循环后，大数排在了后面，小数排在了前面，较后得出的就是一段有序的数列了
时间复杂度
第一层循环循环了 N 次，而第二层循环也循环了 N 次，那么最终的时间复杂度就为:O(N的2次方)
代码
#include<iostream>
#include<cstdio>
using namespace std;
int x[11000000],n;
void bubblesort()//冒泡排序
{
int i,j;
for(i=1;i<=n;i++) for(j=1;j<n;j++) if(x[j]>x[j+1]) swap(x[j],x[j+1]);
//由1至n进行比较,如果顺序不对就交换
}
int **in()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&x);
bubblesort();
for(i=1;i<=n;i++) printf("%d ",x);
return 0;
}冒泡排序的优化
那么我们看到了，冒泡排序的时间复杂度是：O(N的2次方)，是非常慢的，当 N 稍微大一点时，算法就会超时了，所以，我们要想一下如何进行优化。
我们想想，当我们在一轮循环中选出了较大值，就不会有更大的数了，所以说，我们将后面已经不会改变的数进行比较，就显得有些多余了，因此我们可以将这些无用的比较去掉，就能够减少冒泡排序的时间复杂度
我们看到第一层循环，我们可以控制第二层循环的终止点，这样就能够减少时间了
那么，较后的时间复杂度就是：O((N-1)*N/2)
#include<iostream>
#include<cstdio>
using namespace std;
int x[11000000],n;
void bubblesort()//冒泡排序
{
int i,j;
for(i=n;i>=2;--i) for(j=1;j<i;++j) if(x[j]>x[j+1]) swap(x[j],x[j+1]);
//第一层循环由n到2枚举终止点,第二层循环从1到终止点比较,交换不合理的数
}
int **in()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&x);
bubblesort();
for(i=1;i<=n;i++) printf("%d ",x);
return 0;
}那么冒泡排序就讲到这里了
快速排序
接下来就是本次排序算法的重头戏，快速排序从它的字面意思来看，就是它很快 ( 废话 )
算法思想
快速排序通过选取一个基准值，通过比较基准值，将所有符合条件的放在其右侧，其余的放在其左侧，再在左右侧进行排序，如此反复循环，较后就能够将整个序列都排好序了
时间复杂度
快速排序的时间复杂度为：O(N log N)，在排序算法中是非常快的了
递归
使用快速排序就需要用到递归算法，当然递归算**在以后讲到，所以这里就只述说定义
递归算法是利用函数自己调用自己，从而出现一层一层的调用，每一层都是**的，之间的变量不会互相影响，而退出本层递归后就会返回到调用它的函数
递归可以将一个大的问题分解成为小的问题，并进行解决并返回上一层递归，从而得到答案
当然如果还是没听明白也没问题，等之后我再进行详细的讲解，现在只需要明白递归会自己调用自己，每一次的调时的变量都不会相互影响即可
代码
#include<iostream>
#include<cstdio>
using namespace std;
int x[11000000];
void quicksort(int l,int r)
{
if(l>=r) return;//如果出现了不合理的现象就返回上一层函数
int i,j,base;
i=l,j=r;//l是左侧的数的下标,r是右侧的数的下标
base=x[l];//选取基准值,用来比较
while(i<j)//当左侧的
{
while(x[j]>=base&&i<j) j--;//由后往前找到不合理的数,并等待交换
while(x<=base&&i<j) i++;//又前往后找到不合理的数,并等待交换
if(i<j) swap(x,x[j]);//交换它们两个数
}
swap(x[l],x);//较后交换l和i的位置,因为较后i的位置就是基准值最合适的位置
quicksort(l,i-1);//判断最左侧到基准值-1的地方,也就是进行下一次的排序
quicksort(i+1,r);//判断基准值+1到最右侧的地方,也就是进行下一次的排序
}
int **in()
{
int i,n;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&x);
quicksort(0,n);
for(i=1;i<=n;i++) printf("%d ",x);
return 0;
}那为什么要让 j 先动而不是 i 先动呢，如果 i 先动，i 停下来的位置上的数是要比基准数要大的，如果这时进行交换，就会产生错误，如果是 j 先动，则不会产生这样的错误
那么我们接着上面的排序，这时 i 就在 4 处了，随后我们就从递归****下一层递归，开始排序 l 到 i - 1 的范围，因为这里都是有序的了，所以直接跳到 i + 1 到 r 的范围排序
a[6]={1,3,3,4,5,9};较后，整个数列就排好序了
插入排序
插入排序是非常好理解的一种算法，其实这种排序方法在我们的生活中会遇到，例如在打牌时给牌排序就是用这种方法 ( 反正我是用这种方法的 )
算法思想
更给牌排序一样，先选一个数，然后往前找，当发现前面的数要与它本身的大小关系不符时，就交换，否则就将这个数放在这里
通过对每一个数进行替换，最终就会得到一个有序的数列
时间复杂度
插入排序的时间复杂度为：O(N的2次方)
代码
#include<iostream>
#include<cstdio>
using namespace std;
int x[11000000],n;
void insertionsort()//插入排序
{
int i,j;
for(i=1;i<=n;i++) for(j=i-1;j>=1;--j) if(x[j]>x[j+1]) swap(x[j+1],x[j]);
//排序并交换
}
int **in()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;++i) scanf("%d",&x);
insertionsort();
for(i=1;i<=n;++i) printf("%d ",x);
return 0;
}归并排序
归并排序与快速排序类似，都有类似的思想和时间复杂度
算法思想
归并排序算法的思想就是将一段序列拆分，对每两断序列进行排序，这样在排序时就能过确保要不两段序列只有两个值，要不就是两边的序列都是有序的
简单来说，就是将数组往下拆分 (分解)
再将其按照顺序进行组合 ( 合并 )
上面 3 行是分解，下面 3 行是合并
分解
依靠递归实现，每次分半处理，找到只剩两个数或需要合并时进行合并
合并
在需要分解的地方分解完成后就开始合并，因为我们可以确保需要合并的两段数一定是有序的，这样我们可以用这种方法
例如我们需要合并如下两段数列
a[3]={1,5,9};
b[2]={0,10};那么我们是一定确保两段数列是有序的，然后我们用 i 和 j 来代表枚举到的数位，一开始 i 和 j 都为 0，我们依次判断两段数列的第 i 或 j 位的大小，然后将合理的数放入 c 数组中
因为 1 > 0，所以 c 的第一位 k 为 0，然后 j 增加 1，i 不变，继续下一轮判断
因为 1 < 10，所以 c 的第二位 k 为 1，然后 i 增加 1，j 不变，继续下一轮判断
因为 5 和 9 都 < 10，所以 c 的第三四位 k 和 k+1 为 5 和 9，然后 i 增加 2，j 不变，退出判断
但是我们发现，10 还没有加入 c 中，怎么办，我们就可以在较后进行加入，判断 i 和 j 是否到达了数组的末尾，如果没有就进行循环，将较后的末尾传入 c 数组中去
这样，就完成了合并的过程
时间复杂度
与快速排序相同，也是：O(N log N)
代码
#include<iostream>
#include<cstdio>
using namespace std;
int a[100005],b[100005];
long long sum=0;
void mergesort(int left,int right)
//可能会有需要两个函数的归并排序,当然两种代码都是可以的
//这里只是将两个函数的功能放在了同一个函数中
{
if(left>=right) return;//如果左端碰到了右端,就退出本层递归
int mid=(left+right)/2,i=left,j=mid+1,k=left;//初始化
mergesort(left,mid);//继续向下递归
mergesort(mid+1,right);
while(i<=mid&&j<=right)//递归完成后就说明要开始排序了
{
if(a>a[j]) b[k++]=a[j++];//找如果右侧的数要更加小一些就加入进去
else b[k++]=a[i++];//如果左侧的数要更小一些就加入进去
}
while(i<=mid) b[k++]=a[i++];//如果剩下还没有排=排列**的就在这里放入
while(j<=right) b[k++]=a[j++];
for(i=left;i<=right;i++) a=b;//覆盖原数组即可
}
int **in()
{
int i,n;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&a);
mergesort(1,n);
for(i=1;i<=n;i++) printf("%d ",a);
return 0;
}算法库自带的快速排序
以上这些就是比较常用的排序算法，并且快速排序和归并排序对于现阶段来说还是比较难以理解的，况且利用了递归的思想去解决，所以...
#include<algorithm>这就是它需要的参数，看不懂对吧，其实没必要懂，它要求的参数就是数组排序的第一位到较后一位，我们这样子就是将 a 数组的下标为 0 的地方到下标为 n 的地方进行快速排序，即
int a[1000000],i,n;
scanf("%d",&n);
for(i=1;i<=n;i++) sacnf("%d",&a);
sort(a+1,a+n+1);//因为数组默认从0开始,所以这里需要从1开始进行排序,到n+1处停止
for(i=1;i<=n;i++) printf("%d ",a);而如果数组是从 0 开始的，那么，sort 中的加 1 就没有必要写上去了
Scanf 和 Printf
这次加了点别的知识，还不给我个三连，这次来学*一下 scanf 和 printf
我们都知道，C++ 中，我们可以用 cin 和 cout 进行输入输出，当然这可以，但是它会比 scanf 和 printf 慢一些，当我们做一些测试数据非常多的题目时，就会出现超时的现象，所以为了节约时间，我们可以使用更快的 scanf 和 printf，当然如果你还想要更加快的也有，例如快读快写就能过满足需求，当然现在学*的是 scanf 和 printf，暂时不学*快读快写
scanf
public int __cdecl scanf (const char * __restrict__ _For**t, ...)当然没必要记下来，我们只需要知道它里面应该放什么就对了
scanf("%d",&n);其中，逗号前的是一个字符串，里面记录这读入时的限制格式，限制格式有这些是常用的
%d----int,short,bool
%f----float
%lf---double
%lld--long long
%s----char 数组
%c----char值得注意的是，即使我们没有加取地址符，编译时也不会报错，但是在运行中就会崩溃，所以一定要注意加取地址符
printf
public int __cdecl printf (const char * __restrict__ _For**t, ...) printf("%d\n",a);相信你已经注意到了，与 scanf 不同，后序的输出变量不再需要加取地址符了，如**上了取地址符，输出的将会是它的地址
一本通**的讲解
1310 - 1311 , 1176 - 1187
1310：【例2.2】车厢重组
这道题要转车厢，而转动进行排序的方法其实就是冒泡排序，而我们只需使用冒泡排序给车厢进行排序，在记录交换次数即可
#include<iostream>
#include<cstdio>
using namespace std;
int x[10001],sum=0;
int **in()
{
int i,j,n;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&x);
for(i=1;i<n;i++)
{
for(j=i+1;j<=n;j++)
{
if(x>x[j])//判断是否进行交换
{
swap(x,x[j]);//交换
sum++;//累计交换次数
}
}
}
printf("%d\n",sum);//输出交换次数
return 0;
}1311：【例2.5】求逆序对
这道题就利用了归并排序，其实冒泡排序也是能够找出逆序对的，只不过冒泡排序太慢了，过不去 ( 这里就体现算法的时间复杂度的重要性 )
#include<iostream>
#include<cstdio>
using namespace std;
int a[100005],b[100005];
long long sum=0;
void mergesort(int left,int right)//归并排序
{
if(left>=right) return;
int mid=(left+right)/2,i=left,j=mid+1,k=left;//求出中间值
mergesort(left,mid);//递归
mergesort(mid+1,right);
while(i<=mid&&j<=right)//将a按次排列**b数组中
{
if(a>a[j])
{
b[k++]=a[j++];
sum+=mid-i+1;
}
else b[k++]=a[i++];
}
while(i<=mid) b[k++]=a[i++];//放入b数组中
while(j<=right) b[k++]=a[j++];
for(i=left;i<=right;i++) a=b;//将b数组重新放入a中
}
int **in()
{
int i,n;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&a);
mergesort(1,n);
printf("%lld\n",sum);
return 0;
}1176：谁考了第k名
这题可以用冒泡排序进行排序，然后就可以知道第 k 项是哪个了
#include<iostream>
#include<cstdio>
using namespace std;
int a[110];//一个int
float b[110];//一个float
//使用结构体struct更加简单,但是目前并没有学到,所以不使用
int **in()
{
int i,j,n,k;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++) scanf("%d%f",&a,&b);
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if(b<b[j])
{
swap(a,a[j]);//交换
swap(b,b[j]);
}
}
}
printf("%d %g\n",a[k],b[k]);//输出,%g不用管它是什么,直接进行使用
return 0;
}1177：奇数单增序列
这道题其实就是将奇数取出，然后再进行排序
#include<iostream>
#include<cstdio>
using namespace std;
int a[500];
int **in()
{
int n,x,i,j=1;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&x);
if(x&1==1) a[j++]=x;//将奇数取出,还记得这种判断奇数的方法吗
}
n=j-1;//因为每次循环的j较后都会高出1,所以赋值给n时就要减1
for(i=1;i<=n;i++) for(j=i+1;j<=n;j++) if(a>a[j]) swap(a,a[j]);//排序
for(i=1;i<=n;i++)//输出
{
if(i==1) cout<<a;
else cout<<','<<a;
}
return 0;
}1178：成绩排序
这道题就是将冒泡排序的交换判断方式改一下就能够通过
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
string a[21];
int b[21];
int **in()
{
int i,j,n;
scanf("%d",&n);
for(i=1;i<=n;i++) cin>>a>>b;
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if(b<b[j])//如果分数不同
{
swap(a,a[j]);
swap(b,b[j]);
}
else
if(b==b[j]&&a[0]>a[j][0])//相同则按照字典序进行排序
{
swap(a,a[j]);
swap(b,b[j]);
}
}
}
for(i=1;i<=n;i++) printf("%s %d\n",a.c_str(),b);//输出
return 0;
}1179：奖学金
这道题仍然可以用冒泡排序进行排序
#include<iostream>
#include<cstdio>
using namespace std;
int a[400],b[400],c[400],d[400],e[400];//结构体真的很香(下次一定讲)
void superswap(int i,int j)//超级交换...
{
swap(a,a[j]);
swap(b,b[j]);
swap(c,c[j]);
swap(d,d[j]);
swap(e,e[j]);
}
int **in()
{
int i,j,n;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>b>>c>>d;//输入三科
a=b+c+d;//算总分
e=i;//赋值学号
}
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if(a<a[j]) superswap(i,j);//只不过需要判断的东西多了点罢了
else if(a==a[j])
{
if(b<b[j]) superswap(i,j);
else if(b==b[j]&&e>e[j]) superswap(i,j);
}
}
}
for(i=1;i<=5;i++) printf("%d %d\n",e,a);
return 0;
}1180：分数线划定
这道题仍然是利用冒泡排序，值得注意的是，它的分数可能会有相同的，那些相同的分数也要记录下来
#include<iostream>
#include<cstdio>
using namespace std;
int a[40000],b[40000];//结构体是真的香
int **in()
{
int i,j,n,m,sum;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) scanf("%d%d",&a,&b);
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if(b<b[j])
{
swap(a,a[j]);
swap(b,b[j]);
}
else if(b==b[j]&&a>a[j])
{
swap(a,a[j]);
swap(b,b[j]);
}
}
}
sum=m*1.5;
while(b[sum]==b[sum+1]) sum++;//判断分数相同的情况
printf("%d %d\n",b[sum],sum);
for(i=1;i<=sum;i++) printf("%d %d\n",a,b);
return 0;
}1181：整数奇偶排序
这道题就是将奇偶数分开后分别进行排序，然后输出
#include<iostream>
#include<cstdio>
using namespace std;
int a[10],b[10],x,y;
int **in()
{
int i,j,n;
for(i=0;i<10;i++)
{
scanf("%d",&n);
if(n&1) a[x++]=n;//分离奇数
else b[y++]=n;//分离偶数
}
for(i=0;i<x;i++) for(j=i+1;j<x;j++) if(a<a[j]) swap(a,a[j]);//冒泡排序
for(i=0;i<y;i++) for(j=i+1;j<y;j++) if(b>b[j]) swap(b,b[j]);//冒泡排序
//这里就展示了两种不同排序的方法
for(i=0;i<x;i++) printf("%d ",a);//输出
for(i=0;i<y;i++) printf("%d ",b);//输出
return 0;
}1182：合影效果
这道题与上一道题目非常相似，只不过转换了一下排序顺序和更改成为了不确定数量个人罢了
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
int x,y;
float a[41],b[41],c;
string t;
int **in()
{
int i,j,n;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>t>>c;
if(t=="**le") a[x++]=c;//分离男生
else b[y++]=c;//分离女生
}
for(i=0;i<x;i++) for(j=i+1;j<x;j++) if(a>a[j]) swap(a,a[j]);//冒泡排序
for(i=0;i<y;i++) for(j=i+1;j<y;j++) if(b<b[j]) swap(b,b[j]);//冒泡排序
for(i=0;i<x;i++) printf("%.2f ",a);//输出
for(i=0;i<y;i++) printf("%.2f ",b);//输出
return 0;
}1183：病人排队
这道题因为非老人不需要交换，所以我们可以将老人和非老人分开输出，只需进行交换老人即可，因为非老人无需进行交换，它们本身就是按照排列顺序排序的
#include<iostream>
#include<cstdio>
using namespace std;
string id[110];
int a[110],age[110];
void superswap(int i,int j)
{
swap(age,age[j]);
swap(id,id[j]);
swap(a,a[j]);
}
int **in()
{
int i,j,n;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
cin>>id>>age;//输入
a=i;//赋值序号
}
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if(age>=60&&age<age[j]) superswap(i,j);//判断老人的年龄
else if(age==age[j]&&a>a[j]) superswap(i,j);//判断老人的先后顺序
}
}
for(i=1;i<=n;i++) if(age>=60) printf("%s\n",id.c_str());//先输出老人
for(i=1;i<=n;i++) if(age<60) printf("%s\n",id.c_str());//再输出非老人
return 0;
}1184：明明的随机数
这道题概括来说就是去重+排序，将队列中相同的数去掉，这道题可以使用桶计数进行去重，而桶计数刚好又能够对数进行排序，这样就一举两得了
#include<iostream>
#include<cstdio>
using namespace std;
int t[101];
int **in()
{
int i,n,x,sum=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&x);
t[x]++;
}
for(i=1;i<=1001;i++) if(t!=0) sum++;
printf("%d\n",sum);
for(i=1;i<=1001;i++) if(t!=0) printf("%d ",i);
return 0;
}1185：单词排序
这道题的难点在于处理字符串的输入，可能有些人对这种输入形式的题目不太理解
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
string a[110];
int sum;
int **in()
{
int i;
while(cin>>a[sum])
{
for(i=0;i<sum;i++) if(a==a[sum]) break;//如果有则不放入
if(i==sum) sum++;//没有则输入
}
sort(a,a+sum);//用sort进行排序
for(i=0;i<sum;i++) printf("%s\n",a.c_str());//输出
return 0;
}1186：出现次数超过一半的数
这道题，认真看过我以前文章的人肯定想到了桶计数，但是问题又来了，这道题的范围是 -50 到 50，可是数组没有 -50 的下标啊，这时，我们就可以将负数下标转换为正数下标，即将 -50 增加 51，就变成了 1 号，依次类推，在输出时减去 51 即可
#include<iostream>
#include<cstdio>
#include<c**th>
using namespace std;
int t[110];
int **in()
{
int i,n,x;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&x);
t[x+51]++;//利用桶进行计数
}
for(i=1;i<=101;i++)
{
if(t>ceil(n/2))//如果有一个数超过了一半
{
printf("%d\n",i-51);//输出
return 0;
}
}
printf("no\n");//没有则输出"no"
return 0;
}1187：统计字符数
这道题仍然可以使用统计数的方法，而且我们可以将输入的字符减去 96，以减少其占用的空间
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
string x;
int t[27],**xn,letter=1;
int **in()
{
getline(cin,x);
int i,l=x.size();
for(i=0;i<l;i++) t[x-96]++;//减去96,减少占用空间
for(i=1;i<=26;i++) if(t>**xn) **xn=t,letter=i;//找出较大
printf("%c %d\n",char(letter+96),**xn);//输出
return 0;
}好了，这次的排序算法就讲到这里了
文档下载
转载：感谢您阅览，转载请注明文章出处“来源从小爱孤峰知识网：一个分享知识和生活随笔记录的知识小站”。
链接：C++ 基础算法 - 排序算法http://www.gufeng7.com/niaolang/1854.html
联系：如果侵犯了你的权益请来信告知我们删除。邮箱：119882116@qq.com
上一篇： C++ 基础算法 - 高精度
下一篇: C++ 基础算法 - 递推 & 递归
