快速排序

· · 个人记录

快速排序

解决问题场景

将一组无序的数据进行排序，比如数组a[n]，n>10000

算法原理

基本思想——分治：

1. 确定基准值：
选取数组中的一个值作为基准值x，
选取位置可以是数组左端点、右端点、中间点mid=(l+r)/2，或者是随机选取一个位置，记录为x。
2. 调整区间：
目的：通过交换数值，使得整个区间分成左右2部分
区间左边的数都<=x
区间右边的数都>=x
使得整个区间大致有序
3. 递归处理左右区间：
递归调用自己，继续处理左区间、右区间
直到区间长度为1

算法动画展示

快速排序动画

算法复杂度及稳定性

复杂度：与基准值的选择有关，平均复杂度为O(nlogn），最差情况下O(n^2)

稳定性：不稳定

代码模板

#include<bits/stdc++.h>
using namespace std;
const int N=500001;
int n, k, a[N]; 

//将a[]的l到r之间的数据从小到大排序，
void quickSort(int l, int r){
    if(l>r) return;
    int i=l, j=r, x=a[(l+r)/2];
    while(i<=j){
        while(a[i]<x) i++;
        while(a[j]>x) j--;
        if(i<=j){
            swap(a[i], a[j]);
            i++;
            j--;
        } 
    }
    //循环结束后j<i
    if(l<j) quickSort(l,j);
    if(i<r) quickSort(i,r);     
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }   
    quickSort(1, n);
    for(int i=1; i<=n; i++){
        printf("%d ", a[i]);
    }

    return 0;
}