quicksort和mergesort有什么区别？

Question

我是否正确地说,在两种算法中,您所做的只是采用您的结构,递归地将其分成两部分,然后以正确的顺序构建您的结构？

那么区别是什么呢？

编辑:我发现了以下算法在quicksort中实现分区,但我真的不明白它是如何工作的,特别是(hi + low) >>> 1用作参数的swop行!任何人都可以理解这个吗？

private static int partition( int[] items, int lo, int hi ) 
{
    int destination = lo;
    swop( items, (hi + lo) >>> 1, hi );
    // The pivot is now stored in items[ hi ].
    for (int index = lo; index != hi; index ++) 
    {
        if (items[ hi ] >= items[ index ]) 
        {
            // Move current item to start.
            swop( items, destination, index );
            destination ++;
        }

        // items[ i ] <= items[ hi ] if lo <= i < destination.
        // items[ i ] > items[ hi ] if destination <= i <= index.
    }

    // items[ i ] <= items[ hi ] if lo <= i < destination.
    // items[ i ] > items[ hi ] if destination <= i < hi.
    swop( items, destination, hi );
    // items[ i ] <= items[ destination ] if lo <= i <= destination.
    // items[ i ] > items[ destination ] if destination < i <= hi.
    return destination;
}

Answer 1

我是否正确地说,在两种算法中,您所做的只是采用您的结构,递归地将其分成两部分,然后以正确的顺序构建您的结构？

是.然而,不同之处在于结构以正确的顺序构建.在Quicksort中,实际的排序步骤在拆分过程中完成(将元素移动到左侧或右侧,取决于与枢轴元素的比较),并且没有合并步骤来重新启动树(从数据点观察)视图;你的实现当然可以有堆栈展开),而在Mergesort中,排序是在上升的过程中完成的 - 拆分步骤根本不移动元素,但在备份的过程中,你需要合并两个排序的列表.

至于性能比较:Quicksort的最坏情况行为肯定比Mergsesort差,但是平均情况的常数因素(几乎完全在实践中观察到的)较小,这使得Quicksort通常是通用,未分类输入的赢家.并不是很多人需要自己实现通用排序例程......

Answer 2

在最坏的情况下,quicksort将具有O(n ^ 2),其中mergesort将为O(n*log n)

Quicksort使用一个数据透视表,并以枢轴作为参考点对这两个部分进行排序,并存在枢轴将是已排序数组的最大值或最小值的风险.如果您将选择错误的枢轴,您将最终得到复杂性n ^ 2(n ^ 2比较)

命名的Mergesort基于递归地将数组划分为相同大小的一半并将它们合并.例如,对维基百科的相当不错的解释.特别是带有树状刹车的图片似乎很好地解释了它.