快速排序的实现(三种划分元素的实现，双指针

75 阅读 0 评论 50 点赞

我是靠谱客的博主搞怪戒指，最近开发中收集的这篇文章主要介绍快速排序的实现(三种划分元素的实现，双指针，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

众所周知，快速排序的核心是分治的思想，选一个基准出来，然后通过划分操作，使得，该元素最终处于的位置的左边的元素都小于等于它，右边的元素都大于等于它

划分操作就是两次递归嘛，没什么的，关键在于不借助外部空间我们如何实现划分操作

首先我们不知道该元素放在哪里，显然这是最后才能确定的，

我了解到一种填坑法的实现...

那就是首先保存第一个位置的值，然后从后向前扫描第一个小于x的值，我们就可以直接覆盖第一个位置的值，然后我们再从前向后找大于x的值，

把后面的坑填上

下面枚举几种情况

基准前后有相同数量的数

5 6 7 4 1 2 3

因为初始化的原因，我们想选4为基准就需要交换5,4

4 6 7 5 1 2 3

x=4

3比4小，覆盖4

3 6 7 5 1 2 3

从前往后扫，6比4大，覆盖3

3 6 7 5 1 2 6

从后往前扫，2比4小，覆盖6

3 2 7 5 1 2 6

从前往后扫，7比4大，覆盖2

3 2 7 5 1 7 6

从后往前扫，1比4小，覆盖7

3 2 1 5 1 7 6

从前往后扫，5比4大，覆盖1

3 2 1 5 5 7 6

前后有不同数量的数

6 7 4 1 2 3

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=100005;
int n,a[maxn];
// 3 2 8 4 5 3
// 2 2 8 4 5 3
// 
void quick(int l,int r){
    if(l>=r) return;
    int pivot=(l+r)>>1;swap(a[l],a[pivot]);
    int left=l,right=r,x=a[l];
    while(left<right){
        while(right>left&&a[right]>=x)   right--;
        if(right>left) a[left++]=a[right];
        while(left<right&&a[left]<=x)    left++;
        if(left<right) a[right--]=a[left];
    }
    a[left]=x;
    for(int i=0;i<n;++i) printf("%d,",a[i]);printf("n");
    quick(l,left-1);quick(left+1,r);
}
int main(){
    while(~scanf("%d",&n)){
        for(int i=0;i<n;++i) scanf("%d",&a[i]);
        quick(0,n-1);
        for(int i=0;i<n;++i) printf("%d,",a[i]);printf("n");
    }
    return 0;
}

但是这个写法并不能AC，即使我们让x=a[l+rand()%(r-l+1)]

还有一种写法是也是维护两个指针i,j,使得0~i都是小于等于x的数，j~n-1都是大于x的数

初始i=l-1,j=l;如果碰到小于等于x的数，那么我们让a[j]和a[i+1]交换，因为默认a[i+1]是大于x的，交换后

j指针悬停的位置仍然是大于x的，如果碰到大于x的数，我们直接移动j指针将该位置加入大于x的集合

附上代码

实现时注意将最后一个位置空开，最后将i+1这个分界线与a[r]交换，实现时默认基准是a[r]

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 using namespace std;
 5 const int maxn=1e5+7;
 6 int n,a[maxn];
 7 void quick(int l,int r){
 8     if(l>=r) return ;
 9     int x=a[r],i=l-1;
10     for(int j=l;j<r;++j){
11         if(a[j]<=x){
12             i=i+1;
13             swap(a[i],a[j]);
14         }
15     }
16     swap(a[i+1],a[r]);
17     quick(l,i);quick(i+2,r);
18 }
19 int main(){
20     while(~scanf("%d",&n)){
21         for(int i=0;i<n;++i) scanf("%d",a+i);
22         quick(0,n-1);printf("%d",a[0]);
23         for(int i=1;i<n;++i) printf(" %d",a[i]);printf("n");
24     }
25     return 0;
26 }

不过这个仍然不能AC。。。

所以我又学习了另外一种方法，仍然是维护两个指针i,j,使得0~i是小于等于x的数，j~n-1都是大于等于x的数

所以如果碰到前面有大于等于x后面有小于等于x的那么我们就可以交换，并且i向后移动，j向前移动，

因为循环跳出的条件是i>j,那么其实最终j变成了小于等于x的边界，i变成了大于等于x的边界，所以根据这两个边界可以进行递归

如果i,j在同一位置，相互移动跳出循环，其实并不是后面小于等于x的数和前面大于等于x的数成对的

如果不是成对的，那么必有一部分数是完全大于或小于x的，那么这一部分一定会让某一指针连续跳跃而不进行交换

所以这个算法是正确的...附上代码

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #include <cstdlib>
 5 using namespace std;
 6 const int maxn=1e5+7;
 7 int n,a[maxn];
 8 void quick(int l,int r){
 9     int i=l,j=r,x=a[l+rand()%(r-l+1)];
10     while(i<=j){
11         while(a[i]<x) i++;
12         while(a[j]>x) j--;
13         if(i<=j){
14             swap(a[i],a[j]);
15             i++;j--;
16         }
17     }
18     if(l<j) quick(l,j);
19     if(i<r) quick(i,r);
20 }
21 int main(){
22     while(~scanf("%d",&n)){
23         for(int i=0;i<n;++i) scanf("%d",a+i);
24         quick(0,n-1);printf("%d",a[0]);
25         for(int i=1;i<n;++i) printf(" %d",a[i]);printf("n");
26     }
27     return 0;
28 }