以下快速排序方法如何工作？

Question

出于教育目的，我编写了自己的快速排序方法。为了改进它，我查看了 .NET 源代码以了解如何实现 LINQ OrderBy() 方法。

void QuickSort(int[] map, int left, int right) {
    do {
        int i = left;
        int j = right;
        int x = map[i + ((j - i) >> 1)];
        do {
            while (i < map.Length && CompareKeys(x, map[i]) > 0) i++;
            while (j >= 0 && CompareKeys(x, map[j]) < 0) j--;
            if (i > j) break;
            if (i < j) {
                int temp = map[i];
                map[i] = map[j];
                map[j] = temp;
            }
            i++;
            j--;
        } while (i <= j);
        if (j - left <= right - i) {
            if (left < j) QuickSort(map, left, j);
            left = i;
        }
        else {
            if (i < right) QuickSort(map, i, right);
            right = j;
        }
    } while (left < right);
}

我正在尝试了解内部工作原理。据我所知，它看起来与 Hoare partition scheme 非常相似，但有一些细微的优化。

我不清楚的是：

为什么我们在分区后只递归主元的一侧？（取决于 if (j - left <= right - i) 的结果）
为什么我们对整个事情有一个 do { ... } while (left < right)？是因为我们只递归了上面建议的枢轴的一侧吗？
为什么在交换之前有一个 if (i < j) 条件测试？前面的break;语句还不够吗？

相比之下，这是我实际实现 Quicksort 的样子（霍尔分区方案的直接实现）

void QuickSort(int[] map, int left, int right)
{
    if (left < right)
    {
        int i = left - 1;
        int j = right + 1;
        int x = map[left + ((right - left) >> 1)];

        while (true)
        {
            do { i++; } while (Compare(map[i], x) < 0);
            do { j--; } while (Compare(map[j], x) > 0);

            if (i >= j) break;

            int temp = map[i];
            map[i] = map[j];
            map[j] = temp;
        }

        QuickSort(map, left, j);
        QuickSort(map, j + 1, right);
    }
}

Answer 1

Why do we recurse only one side of the pivot after partitionning ? (depending the result of the if (j - left <= right - i) )

最小化递归深度（和堆栈使用）。当我们尽快处理较大的分区并且只对较小的分区进行递归时，深度不会超过 log(n)

Why do we have a do { ... } while (left < right) over the whole thing ?

left 之前和 right 之后的项目已排序，因此这些索引在所有数组排序时相遇

Why is there a if (i < j) conditional test before the swap ?

只是为了避免对相等索引进行不必要的交换

以下快速排序方法如何工作？

How does the following quicksort method works?

c#

linq

algorithm

partitioning

quicksort