快速排序

基本思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法复杂度

最差时间复杂度O(N²)
平均时间复杂度O(NlogN）

实现方法

首先，我们有一串序列需要排序a[10] = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};。
我们现在从序列里面找到一个基准数（任何数字都可以），这里选择a[0]也就是6。
我们先从右往左找到一个小于6的数，再从左往右找到一个大于6的数，然后交换它们。

模版见下

void Quick_sort (int arr[], int left, int right) {
    if (left >= right) {
        return;
    } //递归结束条件
    int Base_Value = arr[(left+right)/2]; //选择基准值
    int i = left - 1;
    int j = right + 1;

    while (i < j) {
        do
            i++;
        while (arr[i] < Base_Value);
        do
            j--;
        while (arr[j] > Base_Value);

        if (i < j)
            swap(arr[i], arr[j]);
    }
    Quick_sort (arr, left, j); //继续排左边的
    Quick_sort (arr, j + 1, right); //继续排右边的
}

图解

更详细的解释可以看下面的文章

AcWing 785. 快速排序算法的证明与边界分析 - AcWing