快速排序算法（三种分区方法要熟练！）

快排确实厉害！！！

总的思想是分治递归，取定一个值作为标签，比该值小的去左边，比该值大的去右边。

单向扫描分区法：

去左边的操作：只将sp++即可。

去右边的操作：具体是将sp指向的值与bigger指向的值交换。

考虑边界：当扫描指针sp与bigger相等时，再执行一次循环后，sp刚好在bigger的右边一格。

/*
 * 快速排序算法
 */
void swp(int arr[], int n, int m)
{
    int temp = arr[n];
    arr[n] = arr[m];
    arr[m] = temp;
}
int Part(int arr[], int p, int r)
{
    int pivot = arr[p]; // 定中间数
    int sp = p + 1;   // 扫描指针
    int bigger = r;   // 右侧指针
    while (sp <= bigger)
    {
        if (arr[sp] > pivot) {
            swp(arr, sp, bigger);
            bigger--;
        }
        else
            sp++;
    }
    swp(arr, p, bigger);
    return bigger;
}
void quickSort(int arr[], int p, int r)
{
    int q = 0;
    if (p < r) {
        // 分区：小于的数移动到左边，大于的数移动到右边
        q = Part(arr, p, r);
        // 将排序问题分治
        quickSort(arr, p, q - 1);
        quickSort(arr, q + 1, r);
    }
}
int main()
{
    int ar[2] = {1, -1};
    quickSort(ar, 0, 1);
    // 打印
    for (int i = 0; i <= 1; i++)
        cout << ar[i] << endl;
    return 0;
}

双向扫描分区法：

与单向扫描分区类似，但left指针一直往右移，直到大于中间值时停止；right指针一直往左移，直到小于中间值时停止。然后left值与right值交换。之后left继续一直左移，right一直右移。重复执行。

小心：left一直左移（或right一直右移）导致的数组越界问题。

/*
 * 快速排序算法
 */
void swp(int arr[], int n, int m)
{
    int temp = arr[n];
    arr[n] = arr[m];
    arr[m] = temp;
}
int Part(int arr[], int p, int r)
{
    int pivot = arr[p]; // 定中间数
    int left = p + 1;  // 左指针
    int right = r;     // 右指针
    // 双向扫描核心
    while (left <= right)
    {
        while (left <= right && arr[left] <= pivot) left++;
        while (left <= right && arr[right] > pivot) right--;
        if (left < right)
            swp(arr, left, right);
    }
    swp(arr, p, right);
    return right;
}
void quickSort(int arr[], int p, int r)
{
    int q = 0;
    if (p < r) {
        // 分区：小于等于的数移动到左边，大于的数移动到右边
        q = Part(arr, p, r);
        // 将排序问题分治
        quickSort(arr, p, q - 1);
        quickSort(arr, q + 1, r);
    }
}
int main()
{
    int ar[8] = {2, 3, 3, 3, 45, 8, 4, 6};
    quickSort(ar, 0, 7);
    // 打印
    for (int i = 0; i <= 7; i++)
        cout << ar[i] << " ";
    return 0;
}

三指针分区法：

三指针分区法对于相等元素较多的数组能提升一定的效率。

Next_Less_Pos指针始终指向数组的相等区第一个元素；Next_Scan_Pos指针始终指向要扫描区域的第一个元素；Next_Bigger_Pos指针的右区域所有元素总大于主元。

/*
 * 快速排序算法
 */
void swp(int arr[], int n, int m)
{
    int temp = arr[n];
    arr[n] = arr[m];
    arr[m] = temp;
}
void Part(int arr[], int p, int &e, int &bigger)
{
    int pivot = arr[p]; // 定中间数
    int s = e;
    // 三指针分区核心
    while (s <= bigger) {
        if (arr[s] < pivot) { 
            swp(arr, s, e);
            s++; e++;
        }
        else if (arr[s] > pivot) {
            swp(arr, s, bigger);
            bigger--;
        }
        else s++; 
    }
    swp(arr, e - 1, p);
}
void quickSort(int arr[], int p, int r)
{
    int left = p + 1, right = r;
    if (p < r) {
        // 分区：小于的数移动到左边，大于的数移动到右边，等于的数在中间
        Part(arr, p, left, right);
        // 将排序问题分治
        if (left > p) quickSort(arr, p, left - 1);
        if (right < r) quickSort(arr, right + 1, r);
    }
}
int main()
{
    int ar[20];
    srand((unsigned)time(nullptr));
    for (int i = 0; i <= 19; i++)
        ar[i] = rand() % (10 - 1 + 1) + 1;
    quickSort(ar, 0, 19);
    // 打印
    for (int i = 0; i <= 19; i++)
        cout << ar[i] << " ";
    return 0;
}

小心边界：必须是相等区域的前一个小于元素，和相等区域的后一个大于元素（即 left - 1 和 right + 1），这时能避免无限循环。

但在避免无限循环的同时，又得保证边界下标的合理性，故我们此时加 if 语句判断。