笔记

找到一个基准，使得左边的元素都比它小，右边的元素都比它大，然后再分别处理基准左边和右边的子数组

注意

不稳定排序

#include<bits/stdc++.h>

using namespace std;


/**
 * 快速排序
 * */

int partition(int a[], int left, int right) {
    int base = a[left];
    while(left < right) {
        while(left < right && a[right] >= base) {
            right--;
        } 
        a[left] = a[right];
        while(left < right && a[left] <= base) {
            left++;
        }
        a[right] = a[left];
    }
    a[left] = base;
    return left;
}
void quick_sort(int a[], int left, int right) {
    if(left >= right) {
        return ;
    }
    int k = partition(a, left, right);
    quick_sort(a, left, k-1);
    quick_sort(a, k+1, right);
}

int main() {
    int a[] = {9, 3, 1, 4, 2, 7, 8, 6, 5};

    int len = sizeof(a)/sizeof(a[0]);

    quick_sort(a, 0, len-1);

    for(int i = 0; i < len; i++) {
        printf("%d%c", a[i], " \n"[i==len-1]);
    }
    return 0;
}

参考链接

快速排序 (opens new window)