快速排序

在排序的数据中选取一个基准值，根据自身需要将大于或小于该基准值的数据放在对应的左右两边，再对左右两边进行如上的分区，直到区间里面只剩下一个是数据
快速排序分为三种：
左右指针法：
给定一个数组，左指针left指向数组的开始位置，右指针right指向数组的最后一个位置，left指针向后找比基准值大的数据，right指针向前找比基准值小的数据，找到之后进行交换，现在将数组分为两部分，再分别对两个分区进行上述操作

//左右指针法
int LRsort(int* arr, int begin, int end)
{
    int left = begin;
    int right = end;
    int key = arr[end];
    while (left < right)
    {
    //left小于right这个条件必须在子while循环中再次判断while循环中只要满足条件就一直加加或减减
    //当条件不满足的时候才会再次进行判断，有可能出现越界
        while (left<right && arr[left] <= key)
        {
            ++left;
        }
        while (left<right && arr[right] >= key)
        {
            -- right;
        }
        swap(arr[left], arr[right]);
    }
    swap(arr[left], arr[end]);
    return left;
}
void Quick_Sort(int* arr, int begin, int end)
{
    if (begin > end)
    {
        return;
    }
    int pos = LRsort(arr, begin, end);
    Quick_Sort(arr, begin, pos - 1);
    Quick_Sort(arr, pos + 1, end);
}

挖坑法：
给定一组数据，选择一个基准值，创建左右指针，如果坑在左边就从右边找比基准值小的往左边换，如果坑在右边就从左边找比基准值大的往右边换；这里指定基准值为数组的最后一个元素，所以先从左边找比基准值大的数值

//挖坑法
int PartSort(int* arr, int begin, int end)
{
    int key = arr[end];
    int left = begin;
    int right = end;
    while (left<right)
    {
        while (left<right&&arr[left] <= key)
        {
            ++left;
        }
        arr[right] = arr[left];
        while (left<right&&arr[right] >= key)
        {
            --right;
        }
        arr[left] = arr[right];
    }
    arr[left] = key;
    return left;
}
void Quick_Sort(int* arr, int begin, int end)
{
    if (begin > end)
    {
        return;
    }
    int pos = PartSort(arr, begin, end);
    PartSort(arr, begin, pos - 1);
    PartSort(arr, pos + 1, end);
}

前后指针法：
给定一组数据，选定一个基准值，创建两个指针cur，prev分别指向数组的第一个位置和前一个位置，cur向后找比基准值小的数值，找到之后和++prev的位置的数值进行交换，prev指向的是比基准值小的数值

//前后指针法
int UDsort(int* arr, int begin, int end)
{
    int key = arr[end];
    int cur = begin;
    int prev = begin - 1;
    while (cur<end)
    {
        //当++prev等于cur时就不用进行交换，prev已经指向小的数值，交换的目的就是让prev指向小的数值，所以直接对cur进行加加即可
        if (arr[cur]<key&&++prev != cur)
        {
            swap(arr[prev], arr[cur]);
        }
        ++cur;
    }
    swap(arr[++prev], arr[end]);
    return prev;
}
void Quick_Sort(int* arr, int begin, int end)
{
    if (begin > end)
    {
        return;
    }
    int pos = UDsort(arr, begin, end);
    UDsort(arr, begin, pos - 1);
    UDsort(arr, pos + 1, end);
}