最常用的排序 ---快速排序
相对于桶排序，节省了空间，相对于冒泡排序，节省了时间，可谓是两者兼顾的一种更优化的算法
实现：假设有 初始序列"6 1 2 7 9 3 4 5 10 8"。那么从初始序列的两端开始探测。先从右往左找到一个比6小的数，然后在从左往右找到一个比6大的数，然后交换他们。 “6 1 2 5 9 3 4 7 10 8” 这里可以用两个变量i，j，分别指向序列的最左边和最右边。我们这里叫这两个变量为“哨兵i” 和“哨兵j”。
第一次交换结束后。接下来哨兵j继续向左挪移，找到比“基数6”小的后停下来，然后“哨兵i”移动，然后交换
然后在次挪移的时候，发现“哨兵i” 跟 “哨兵j” 相遇了。都走到了3的前面，说明此时“探测”结束。我们将6和3进行交换。
3** 1 2 5 4 6 9 7 10 8” 至此第一轮“探测”结束 ， 此时以基准数 6 为分界点，6左边的数都小于等于 6,6右边的数都大于等于 6。
此时基准数 6 已经归位，他正好处在序列 的第六位，此时我们已经将原来的序列，以6为分界线拆分 成了两个序列，左边的序列是 “3 1 2 5 4”，右边的序列是“9 7 10 8” ，接下来还要分别处理之和两个序列 ， 因为6左边跟右边的序列目前还都是 很混乱的。
后续的处理就是只要模拟刚才的方法分别处理6两遍的序列即可 。
#include<bits/stdc++.h>
#define maxn 105
using namespace std;
int a[maxn];
void qksort(int left,int right){
int i,j,flag;//两哨兵与基准数
if(left>right){
return;
}
flag = a[left];
i = left;
j = right;
while(i!=j){
while(a[j]>=flag&&i<j){
j--;
}
while(a[i]<=flag&&i<j){
i++;
}
if(i<j){
swap(a[i],a[j]);
}
}
a[left] = a[i];
a[i] = flag;
qksort(left,i-1);
qksort(i+1,right);
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
qksort(1,n);
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
} 本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-05-14 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读