了解Quicksort实现

Question

我在浏览不同的quicksort实现时在网上找到了这个代码:

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,正好用于高和低.我认为你想要使用left,pivotIndex和pivotIndex,对.我试过这个并没有用,但我真的不明白为什么.我在其他语言中发现了更多相同的内容,所以我猜它是正确的(它似乎工作,这也是一个很好的指示,它的工作正常).我也不明白为什么每个人似乎都存储了pivot的值而不是pivot的索引.如果我修改它以使用数据透视表的索引而不是似乎也可以工作的值,但是他们这样做似乎相当重要,而快速排序的许多其他实现也是这样做的.有人可以帮我理解这个吗？

Answer 1

该代码实际上是quicksort的一个相当清晰的实现.除了排序算法之外,我整整一个夏天都在工作,所以这个问题引起了我的注意.

理解这个特定程序的关键是每个递归函数调用都接收相同的完整字符串.因此,函数必须设置自己的边界,即"left"和"right",并忽略字符串的其余部分.每个递归函数调用仅处理对字符串的一小部分进行分区.

原始函数调用将字符串分成小于枢轴(下部)和大于枢轴(上部)的部分,留下任何字符串值等于左边和右边部分之间的"无人区域"中的枢轴.

一旦它进入递归函数调用,它就会变得更加模糊,重要的是要理解这些下部和上部与"左"和"右"变量不同."left"变量是函数调用应该操作的整个字符串左边界的原始位置,类似于"right"变量.

该算法的关键是理解第一个函数调用不会在上部或下部分别排序.但是,它会从考虑中删除一个或多个分区值,并确保它们高于所有较低的字符串值,并且低于所有较高的字符串值,即在字符串的"中间".

在串的未排序的上部和下部两者上递归地重复该过程,直到最终达到两个或更少值的上部或下部大小,这些值必须作为分区的结果已经被分类.

如果枢轴值总是极值,则快速排序算法具有O(N ^ 2)的最差情况性能,并且如果枢轴值接近字符串的中间,则最佳情况性能为O(N log N).例如,当排序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是一个非常好的算法,并且非常难以改进,只要一个人的算法避免故意有害的情况,否则可以利用这些情况来为已知的代码库提供输入,该输入产生极值的枢轴序列.