思想

从当前排序的序列中选定一个基准值。设置两个指针分别指向当前排序的序列的头、尾。让这两个指针向中间靠拢，直到它们相遇。在扫描的过程中，要保证以下条件：

左侧指针扫过的区域全部小于等于基准值；
右侧指针扫过的区域全部大于等于基准值；

这样一来，就相当于找到了基准值该在的位置。递归排序左右序列即可。

分析：以选取当前序列首元素为基准值为例

如何满足上述扫描条件？

先让右侧指针持续地向左移动，直到它遇到了不符合条件的数为止；然后让左侧指针持续地向右移动，若它遇到了右指针或遇到了不符合条件的数，就停下来。此时有两种情况：（能够证明：以下两个“若”不会同时发生）

若左指针因为遇到了不符合条件的数而停下：此时左右指针都被“困住”，若不做出改变，都无法继续前进。因此可以让这两个不符合条件的数做一次交换，这样它们就分别符合左右条件了。接下来可以继续循环。
若左指针因为遇到了右指针而停下：相遇点左侧的值都小于等于基准值，相遇点右侧的值都大于等于基准值，这就说明我们找到了基准数该在的位置。接下来交换基准数和相遇点的数即可。

选取当前序列首元素为基准值时，为什么要先移动右指针?

这样的操作使得当左指针碰到之前停下来的右指针时，这个相遇点是不符合右指针条件的。换言之，就是相遇点小于基准值。这样一来，交换过后，之前的“相遇点”就落在了基准值的左侧，满足“基准值左侧的数都小于等于基准值”的思想。

规避最坏情况

有时可以构造特殊数据使得快排的平均复杂度$O(n\log n)$退化成$O(n^2)$。

方案：随机选取基准值

每一次递归都随机选取某个基准值。然后把它交换到序列首位。这样就可以按照序列首位为基准值的算法继续了。

代码

#include <stdio.h>

void mqsort(int *begin, int *end);
void swap(int *x, int *y);

int arr[100000];

void mqsort(int *begin, int *end)
{
    if (end - begin <= 1)
    {
        return;
    }
    swap(begin, begin + (end - begin) / 2);
    int *p = begin;
    int *a = begin, *b = end - 1;
    while (a != b)
    {
        if (*p <= *b)
        {
            --b;
            continue;
        }
        if (*a <= *p)
        {
            ++a;
            continue;
        }
        swap(a, b);
    }
    swap(p, a);
    mqsort(begin, a);
    mqsort(a + 1, end);
}

void swap(int *x, int *y)
{
    int t;
    t = *x;
    *x = *y;
    *y = t;
}

Last modified on 2020-05-14