相对于桶排序,节省了空间,相对于冒泡排序,节省了时间,可谓是两者兼顾的一种更优化的算法
实现:假设有 初始序列"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;
}