快速排序让我感到困惑

Question

目前我正在学习快速排序。我已经遵循了快速排序的规则，但是发现了一件奇怪的事情。

这个过程就像这张图片一样:

请帮我找到我的错误所在:

这是代码:

  static void QuickSortFromMiddle(int[] arr, int low, int high)
    {

        if (low < high)
        {
            int middleValue = arr[(low+high)/2];
            int h = high+1;
            int l = low-1;
            while (l < h)
            {
                while (arr[--h] > middleValue && l<h);

                while (arr[++l] < middleValue && l<h) ;

                if (l >= h)
                    break; 
                int temp = arr[l];
                arr[l] = arr[h];
                arr[h] = temp;

            }

            QuickSortFromMiddle(arr,low,l-1);
            QuickSortFromMiddle(arr, h+1, high);
        }

    }
    /// <summary>
    /// 
    /// </summary>
    static void QuickSort(int[] arr)
    {
        QuickSortFromMiddle(arr, 0, arr.Length - 1);
    }

    /// <summary>
    /// 
    /// </summary>
    static void TestQuickSort()
    {

        var arr = new[] { 1, 5, 3, 4, 57, 5, 5, 53 };
        QuickSort(arr);
        foreach (int i in arr)
        {
            Console.WriteLine(i);
        }
    }

这里是结果（我很困惑...）

如Dukeling所说，“枢轴点通常移动到两端之一”

首先，我应该将枢轴点放置在数组的末尾

其次，我应该将枢轴点放置在arr的正确位置（大于左侧，小于右侧）

正确的过程如下：

- Frank.Liu

---

你是否在调试器中逐行运行它，以查看它的功能并了解为什么会出现错误？ - Sami Kuhmonen

是的，我试过了； 原始数组：1、5、3、4、57、5、5、53 第一次后，结果为：1、4、3、5、57、5、5、53（就像图片一样） - Frank.Liu

尝试使用这个快速排序可视化工具来理解它的工作原理，然后通过逐步观察来比较自己代码的调试器会话。 - Oliver

哇~ 这是一篇好文章，我会看一下，然后调试它，非常感谢~ - Frank.Liu

通常将枢轴移动到两端，以避免必须专门为其提供服务或将其移动到一堆中增加复杂性。在您的示例中，您还需要交换3和4。 - Bernhard Barker

Answer 1

作为 Parakram 所写，枢轴元素是您的主要问题。 该算法不会在数组中间或枢轴元素位置处拆分数组，而是将数组拆分为两个部分，枢轴值位于它们之间。搜索将拆分的位置需要用到 l 和 h。当它们相遇时，就得到了拆分的位置。

我在您的代码中添加了一些注释。我认为这个代码是可行的。

    static void QuickSortFromMiddle(int[] arr, int low, int high)
    {
        Console.WriteLine("Low: {0}, High: {1}, Arr: {2}", low, high, string.Join("|", arr));
        if (low < high)
        {
            int pivot = arr[high]; // Select you pivot element. After the run all smaller numbers will be left of it, all bigger ones on the high-side.
            int h = high;
            int l = low;

            // breaks at specific condition within the loop
            while(true)
            {
                // Search for the first element which is smaller, beginning on the high-side
                while (arr[h] >= pivot && l < h)
                {
                    h--;
                }

                // Search for the first element which is bigger, beginning on the low-side
                while (arr[l] < pivot && l < h)
                {
                    l++;
                }

                // we now have pivot (still at position "high")
                // we got an element which is bigger that pivot on "l"
                // we got an element which is smaller than pivot on "h"
                // conclusion: we need to change their positions

                Console.WriteLine("h: " + h + ", l: " + l +  ", Arr: " + string.Join("|", arr));

                // if l&h are at the same position, we're done and have to check if the pivot element has to be moved to this position
                if (l >= h)
                    break;

                // we change elements on position l and h, because we know that arr[l] is bigger that our pivot and arr[h] is smaller.
                int temp = arr[l];
                arr[l] = arr[h];
                arr[h] = temp;

            }

            // l equals h. This is now the position for pivot, because all elements on the lower side are smaller and all elements on the right side are bigger
            Console.WriteLine(">h: " + h + ", l: " + l + ", Arr: " + string.Join("|", arr));
            if (arr[l] > pivot)
            {
                arr[high] = arr[l];
                arr[l] = pivot;
            }

            // We start two new runs. One for the lower values: from Low to l and from l+1 to high.
            // Why? As we know l is our pivot value which splits the elements into two groups. smaller ones on the lower side, bigger ones on the higher side.
            // We now can focus on those two groups separately.
            QuickSortFromMiddle(arr, low, l);
            QuickSortFromMiddle(arr, l + 1, high);
        }

    }

- kara

---

Kara，我发现你的发型很酷（我无法想象你是一名程序员）；感谢你的测试代码和建议；经过深思熟虑，我在我的问题中加入了正确的流程，你可以看到它~ - Frank.Liu

Answer 2

总体算法如下：

1. 从数组中选择一个元素作为枢轴。
2. 划分：重新排列数组，使所有值小于枢轴的元素在枢轴之前，所有值大于枢轴的元素在枢轴之后（相等的值可以任意处理）。在此划分之后，枢轴位于其最终位置。这被称为划分操作。
3. 将上述步骤递归地应用于具有较小值的元素子数组和具有较大值的元素子数组。

有几种划分方案可供选择，只要满足条件即可。您的划分方案是我从未见过的。特别是，我从未见过以中央位置的值作为枢轴的快速排序划分方案。 请参阅维基百科页面了解一些标准的划分方案（例如Lomuto）。

总的来说，您的划分方案有以下限制：

1. 它假设中央元素（在位置上）是中位数。
2. 它不允许任意定位小于或大于中位数的元素。例如，在交换 arr[l] 和 arr[h] 之前，您甚至不检查它们是否需要交换。您只是假设在移动 l 和 h（两个内部 while 循环）后，所有其他数字都需要被交换。

您需要使您的分区方案更通用，或许尝试理解并使用其中一个标准方案。

- Parakram Majumdar

---

在我看来，“以中心位置的值作为枢轴”与此无关。我们可以选择数组中的任何值作为枢轴；但是我们应该将枢轴放在数组的末尾或开头，我给出了正确的过程（您可以看到问题，我已经给出了正确的过程）。 - Frank.Liu