代码

注意，这里的mqsort函数接受的参数是左闭右开的。

void mqsort(int *begin, int *end)
{
    if (end - begin <= 1)
    {
        return;
    }

    int *i = begin, *j = end - 1;
    int pivot = *(begin + (end - begin) / 2);
    while (i <= j)
    {
        while (*i < pivot)
        {
            ++i;
        }
        while (*j > pivot)
        {
            --j;
        }
        if (i <= j)
        {
            swap(i, j);
            ++i;
            --j;
        }
    }

    mqsort(begin, j + 1);  //写 j + 1 只是因为是左闭右开。
    mqsort(i, end);
}

分析

移动左右指针的过程

内部用小循环来移动两根指针。注意，内部两个移动指针的循环的条件是严格的小于号和大于号，但是移动完的结果是i左侧的值小于等于pivot的，j情况类似。原因：两个小循环都结束时，有*j <= pivot <= *i，后续进行了交换，那么就有*i <= pivot <= *j。

注意到内部两个循环没有判断i和j是否越界，这样不危险吗？没问题！因为pivot本身就是数列中的一项，两个指针最不济也会因为碰到pivot而停下来。

对大循环中最后的 if 的理解

情况一：i == j

这种情况下首先swap语句就等于没有。

此时由于上面两个循环都结束，可以保证*j <= pivot <= *i，且在此种情况下*i == *j,于是*i == *j == pivot。这时++i并--j，使得下次的大循环直接退出，且i和j中间隔了一个元素，正好是pivot。这时序列就被pivot分为了左、中（一个元素）、右三部分。递归排序左右部分即可。

情况二：i + 1 == j

i 和 j 相邻。此时交换后执行 ++i 和 --j，使得它俩刚好“错开”，即j位于i的左侧，且二者还是相邻。

此后j及其左侧都是小于等于pivot的，i及其右侧都是大于等于pivot的。这时的序列被分为两部分，递归排序这两个子序列即可。

情况三：i > j

这种情况下if中语句并不会执行。

由于循环维护的性质，从begin到i的元素都是小于等于pivot。从j到end - 1的的元素都是大于等于pivot的。那么j < i时，中间的公共元素值必定都将是pivot。

这就将序列分成了三部分：左部分、中间若干个pivot、右部分。递归排序左右两个部分即可。

情况四：i + 2 == j

此时i和j之间隔了一个数。按照程序操作后，两个指针就碰面了。在下一次循环中便会落入情况一。

情况五：i < j 且中间隔了不止一个数

操作后，下一次循环时仍是平凡的情况。

Last modified on 2020-05-14