快速排序

排序流程：

1. 每次选区第一个的数为基准数
2. 然后将大于和小于基准的元素分别置于基准数两边
3. 继续分别对基准数两侧未排序的数据使用分治法进行细分处理(分而治之)，直至整个序列有序。

如下图所示：

代码实现:

#include<iostream>
using namespace std;

void print(int* arr, int len)
{
    for (int i = 0; i < len; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int parttion(int arr[], int low, int high)
{
    int i = low;//从左边开始
    int j = high;//从右边开始

    int base = arr[low];//定左边第一个为基准书，拿出来之后，该位置就可以被覆盖了

    //如果low就是最
    if (low < high)
    {
        //左找一个，右找一个......
        while (i < j) //i == j说明已经查找完毕
        {
            while (i < j && arr[j] >= base)//从右边开始遍历，比基准值大，不做改变，继续遍历，直到碰到比基准值小的
            {
                j--;
            }
            if (i < j)//右边找到小于基数的数
            {
                arr[i++] = arr[j];

            }
            while (i < j && arr[i] < base)//从左边开始遍历，比基准值小，不做改变，继续遍历，直到碰到比基准值大的
            {
                i++;
            }
            if (i < j)//左边已经找到大于基数的数
            {
                arr[j--] = arr[i];
            }
        }
        //查找完毕
        //将基准值放入它应该在的位置
        arr[i] = base;
    }   
    //返回基准值位置
    return i;
}

void QuickSort(int* arr,int low, int high)
{
    if (low < high)
    {
        int index = parttion(arr, low, high);//寻找基准值，然后开始分而治之
        //index这个位置的数已经是它该放的位置
        QuickSort(arr, low, index - 1);
        QuickSort(arr, index + 1, high);
    }
}

int main(void)
{
    int arr[] = { 3,1,4,5,5,4,1,3 };
    int len = sizeof(arr) / sizeof(arr[0]);
    QuickSort(arr, 0, len - 1);
    print(arr, len);
    return 0;
}