[编程笔记]-Quick_Sort快速排序

原理

原始版

利用分治思想，新建两个数组，分别储存原数组中小于 X 或大于 X 的元素，并分别对其进行快速排序，最后重组原数组即可。（X可为任意值，推荐使用中值）

进化版

利用分治思想以及部分双指针思想，左右各两个指针，记为 i, j。左指针一直向右，直到数组中第 i 个元素大于 x；右指针一直向左，直到数组中第 j 个元素小于x；接着左右指针对应元素互换，重复执行直到左右指针相遇。

复杂度

平均O(nlogn)，最大O(n²)

代码

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;

int n;
int q[N];

void quick_sort(int q[],int l,int r){
    if(l>=r)return;
    int x=q[l+r>>1],i=l-1,j=r+1;
    while(i<j){
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j)swap(q[i],q[j]);
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&q[i]);
    quick_sort(q,0,n-1);
    for(int i=0;i<n;i++)printf("%d ",q[i]);
    return 0;
}

完结撒花o(￣︶￣)o