首页 > 代码库 > 快速排序的实现(不保证效率

快速排序的实现(不保证效率

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

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

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

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

那就是首先保存第一个位置的值,然后从后向前扫描第一个小于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;
}

 

快速排序的实现(不保证效率