Quick sort

快速排序，顾名思义，在所有排序方法中它是最快的，先说一个它的时间复杂度是O(nlog2N), 虽然也有其他排序方法的时间复杂度也是这个（例如堆排序），但是快排的常数项是最小的。

先来看一下代码 =

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <vector>
#include <algorithm>
#include "dbg.h"
using namespace std;

void quickSort(int[], int, int);

int main(int argc, char *argv[])
{
    int R[] = {49, 38, 65, 97, 76, 13, 27, 49};
    cout << "sort before = " << endl;
    dbg(R);
    int len = sizeof(R) / sizeof(R[0]);
    quickSort(R, 0, len - 1);

    cout << "sort after = " << endl;
    dbg(R);
    return 0;
}

void quickSort(int R[], int low, int high)
{
    int temp;
    int i = low, j = high;
    if (low < high)
    {
        temp = R[low]; // 枢轴
        while (i < j)
        {
            while (j > i && R[j] >= temp) j--; // 从右往左扫描
            if (i < j)
            {
                R[i] = R[j];
                i++;
            }

            while (i < j && R[i] < temp) i++; // 从左往右扫描
            if (i < j)
            {
                R[j] = R[i];
                j--;
            }
        }
        R[i] = temp;
        quickSort(R, low, i - 1);
        quickSort(R, i + 1, high);
    }
}

运行结果如下(文章中显示变量使用的是dbg)

quick_sort

说一个具体的思路 =

首先，找到一个数字作为比较的枢轴，这里使用的是数组最左端的数字，使用temp暂存，现在最左端相当于挖了一个坑（因为当前数字已经赋值给temp了).
从右往左扫描数组，找到比枢轴小的数字，将这个数字赋值给枢轴所在位置(填左边的坑, 同时在右边挖了一个坑)
从左往右扫描数组，找到比枢轴大的数字，将这个数字赋值给右边挖的坑。

这个排序方法使用的分治的思想，英文叫做divide and conquer，分割之后再去克服每一项。递归也是属于这一种。就是将一个大问题分解成相似的小问题，然后解决了其中的一个小问题后，使用类似的方法就解决了所有的问题。

2020/09/30