c# - 对快速排序感到困惑

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的右边(大于左边，小于右边)

这是正确的过程:

Answer 1

整体算法如下:

1. 从数组中选择一个称为枢轴的元素。
2. 分区:对数组重新排序，使所有值小于主元的元素都在主元之前，而所有值大于主元的元素都在主元之后(相等的值可以任意排列)。在此分区之后，枢轴位于其最终位置。这称为分区操作。
3. 递归地将上述步骤应用于值较小的元素子数组，并分别应用于值较大的元素子数组。

分区有多种方案，只要满足条件，任何一种方案都可以。您的分区方案是我以前从未见过的。特别是，我从未见过将位于中心的值作为枢轴的快速排序分区方案。 请看the wikipedia page对于一些标准分区方案(例如 Lomuto)。

总体而言，您的分区方案存在以下限制:

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

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