c# - 了解Quicksort实现

Question

在浏览不同的快速排序实现时，我在网上找到了此代码：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Quicksort
{
    class Program
    {
        static void Main(string[] args)
        {
            // Create an unsorted array of string elements
            string[] unsorted = { "z","e","x","c","m","q","a"};

            // Print the unsorted array
            for (int i = 0; i < unsorted.Length; i++)
            {
                Console.Write(unsorted[i] + " ");
            }

            Console.WriteLine();

            // Sort the array
            Quicksort(unsorted, 0, unsorted.Length - 1);

            // Print the sorted array
            for (int i = 0; i < unsorted.Length; i++)
            {
                Console.Write(unsorted[i] + " ");
            }

            Console.WriteLine();

            Console.ReadLine();
        }

        public static void Quicksort(IComparable[] elements, int left, int right)
        {
            int i = left, j = right;
            IComparable pivot = elements[(left + right) / 2];

            while (i <= j)
            {
                while (elements[i].CompareTo(pivot) < 0)
                {
                    i++;
                }

                while (elements[j].CompareTo(pivot) > 0)
                {
                    j--;
                }

                if (i <= j)
                {
                    // Swap
                    IComparable tmp = elements[i];
                    elements[i] = elements[j];
                    elements[j] = tmp;

                    i++;
                    j--;
                }
            }

            // Recursive calls
            if (left < j)
            {
                Quicksort(elements, left, j);
            }

            if (i < right)
            {
                Quicksort(elements, i, right);
            }
        }

    }
}

我知道几乎所有的函数都是如何工作的，但我想知道为什么在递归调用中，它们使用left、j和i，right表示high和low。我认为您应该使用左边的数据透视索引和右边的数据透视索引我试过但没用但我不明白为什么我在其他语言中发现了更多这样做的语言，所以我猜它是正确的（而且它似乎起作用了，所以这也是一个很好的指标，表明它是正确的）。我也不明白为什么每个人似乎都在存储数据透视的值，而不是数据透视的索引。如果我修改它以使用轴心点的索引，而不是似乎也可以工作的值，但它们这样做和许多其他QuickSort实现以同样的方式这样做似乎相当重要。有人能帮我理解吗？

Answer 1

这段代码实际上是quicksort的一个相当清晰的实现整整一个夏天，我只研究排序算法，所以这个问题引起了我的注意。
理解这个特殊程序的关键是每个递归函数调用都接收相同的完整字符串。因此，函数必须设置自己的边界，即“左”和“右”，并忽略字符串的其余部分每个递归函数调用只处理对字符串的一小部分进行分区。
原始函数调用将字符串划分为小于枢轴（下半部分）和大于枢轴（上半部分）的部分，在左右半部分之间的某个位置保留与“无人区”中的枢轴相等的任何字符串值。
一到递归函数调用，它就变得有点模糊，重要的是要理解这些上下部分不同于“左”和“右”变量。“left”变量是函数调用应该操作的整个字符串左边界的原始位置，与“right”变量类似。
算法的关键是理解第一个函数调用不必在上下部分留下任何排序但是，它会从考虑中删除一个或多个分区值，并确保它们高于所有较低的字符串值，低于所有较高的字符串值，即位于字符串的“中间”。
这个过程在字符串的未排序的上下部分递归地重复，直到最终达到两个或更少值的上下部分大小，而这些值必须已经作为分区的结果进行排序。
如果轴心值始终是极值，则快速排序算法的最坏情况性能为o（n^2）；如果轴心值接近字符串中间，则快速排序算法的最佳情况性能为o（n logn）。例如，当对31个字符进行排序并假设轴的中值选择是完美的，
第一阶段：
下15，枢轴，上15
第二阶段：
（下部7，枢轴，上部7），枢轴，（下部7，枢轴，上部7）
第三阶段：
（（下3，枢轴，上3），枢轴，（下3，枢轴，上3）），枢轴，（（下3，枢轴，上3），枢轴，（下3，枢轴，上3））
第四阶段：
（（下1，枢轴，上1），枢轴，（下1，枢轴，上1）），枢轴，（（下1，枢轴，上1），枢轴，（下1，枢轴，上1）），枢轴，（（下1，枢轴，上1），枢轴，（下1，枢轴，上1）），枢轴，（（下1，枢轴，上1），枢轴，（下1，枢轴，上1）））
四个阶段小于或等于31的底2对数，并且在每个阶段算法是线性的（尽管在每个级别的多个不同递归函数调用中执行），因此执行31个步骤，即n个步骤。
因此，算法的总阶数为4级乘以31，或近似n次log n。
实际上，有时轴不是中值，甚至可能是极值，在这种情况下，“下”或“上”部分是空的。该算法可能在每个阶段仅从考虑中移除一个值，从而导致总共N-1个阶段来完成该算法在每个阶段，都有N个工作步骤，所以总的阶数是N次（N-1），也就是O（N^2），因为N与N是乘积。
您可以在此处看到1000万项排序操作的嵌套列表：
http://www.myersdaily.org/joseph/unix/sort/in10.html
在这里阅读我对unix上的quicksort算法所做的一些观察：
http://www.myersdaily.org/joseph/unix/sort.html
（通过使用无分布统计数据来避免出现“幸运”的情况，这一数据提高了微不足道的7%）。
总之，quicksort是一个非常好的算法，而且很难改进，只要一个人的算法避免故意的有害情况，否则可能会被利用来为已知的代码库提供产生极值轴序列的输入。