——快速排序
快速排序
基本思路
选取中间位置为基准从两边开始遍历，（这里以从小到大为例）左边·遇到第一个大于基准数的记录下标，右边遇到第一个小于基准数的记录下标，然后交换这两个数，重复以上操作直至到达中间位置（***说明一下为啥选取中间位置为基准，假如选取第一位数为基准，假如右边的都比他小，运算量增大，这样时间复杂度会变高）***然后，以基准数为分界线，将区间分成两部分，每个区间重复以上操作。
以洛谷P1177 【模板】排序为例
将读入的 N 个数从小到大排序后输出。
输入格式
第一行为一个正整数 N
第二行包含 N 个空格隔开的正整数 a i，为你需要进行排序的数。
输出格式
将给定的 N 个数从小到大输出，数之间空格隔开，行末换行且无空格。
若不选取中间数为基准便会超时。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+30;
int k[N];
void kp(int l,int r)
{
if(l>r)return ;//排序完成结束条件
int re=r,le=l;
int te=k[(r+l)/2];//选取基准数
while(le<=re)
{
while(k[le]<te)le++;
while(k[re]>te)re–;
if(le<=re)
{
swap(k[le],k[re]);
le++;re–;
}
}
kp(l,re);
kp(le,r);
}
int main()
{
int n;cin>>n;
for(int i=0;i<n;i++)
cin>>k[i];
kp(0,n-1);
for(int j=0;j<n-1;j++)
cout<<k[j]<<" ";
cout<<k[n-1]<<endl;
return 0;
}