三个值策略的中位数

Question

在快速排序中选择枢轴值的三种策略的中位数是多少？

我在网上看到它,但我无法弄明白究竟是什么？以及它如何比随机快速排序更好.

Answer 1

您可以查看数组的第一个,中间和最后一个元素的中位数,并选择这三个元素的中位数作为支点.

为了获得三个中值的"完全效果",对这三个项进行排序也很重要,不仅仅使用中位数作为枢轴 - 这不会影响当前迭代中选择的枢轴,但可以/将影响在下一个递归调用中用作枢轴的内容,这有助于限制一些初始排序的不良行为(在许多情况下结果特别糟糕的是一个已排序的数组,除了具有最小元素的数组)数组的高端(或低端的最大元素).例如:

与随机选择枢轴相比:

1. 它确保一个常见情况(完全排序的数据)保持最佳状态.
2. 操纵最坏的情况更难.
3. PRNG通常相对较慢.

第二点可能有更多的解释.如果你使用了明显的(rand())随机数生成器,那么对于某些人来说,安排这些元素是相当容易的(对很多情况而言),所以它会不断选择不好的枢轴.这可能是一个严重的问题,例如Web服务器可能正在排序潜在攻击者输入的数据,他们可能通过让您的服务器浪费大量时间对数据进行排序来安装DoS攻击.在这种情况下,您可以使用真正随机的种子,或者您可以包含您自己的PRNG而不是使用rand() - 或者您使用三个中位数,这也具有提到的其他优点.

在另一方面,如果你使用了足够的随机数发生器(例如,硬件发生器或加密柜台模式),它可能更难以给力不好的情况下比是三个选择中位数.同时,实现这种随机性通常会带来相当大的开销,所以除非你真的希望在这种情况下受到攻击,否则它可能不值得(如果你这样做,它可能值得至少考虑一个保证O(N log N)最坏情况的替代方案,例如合并排序或堆排序.

Answer 2

想得更快... C 示例....

int medianThree(int a, int b, int c) {
    if ((a > b) ^ (a > c)) 
        return a;
    else if ((b < a) ^ (b < c)) 
        return b;
    else
        return c;
}

这使用按位运算XOR符。所以你会读到：

• 是否a大于唯一的其他之一？return a
• 是b小于专别人的呢？return b
• 如果以上都不是： return c

请注意，通过切换该b方法的比较也涵盖了某些输入相等的所有情况。同样，我们重复相同的比较的a > b方式与 相同b < a，智能编译器可以重用和优化它。

中值方法更快，因为它会导致数组中更均匀的分区，因为分区是基于主元值的。

在随机选择或固定选择的最坏情况下，您会将每个数组划分为一个仅包含主元的数组和另一个包含其余部分的数组，从而导致 O(n²) 复杂度。

使用中位数方法可以确保不会发生这种情况，而是引入了计算中位数的开销。

编辑：

基准测试结果显示XOR比Bigger即使我优化得更大一点也快 32 倍：

您需要回想一下，XOR它实际上是 CPU 算术逻辑单元 (ALU) 的一个非常基本的运算符，然后虽然在 C 中它可能看起来有点笨拙，但在引擎盖下它正在编译为非常有效的XOR汇编运算符。

Answer 3

三个中位数的实现我发现在我的快速排序中运作良好.

(Python)
# Get the median of three of the array, changing the array as you do.
# arr = Data Structure (List)
# left = Left most index into list to find MOT on.
# right = Right most index into list to find MOT on

def MedianOfThree(arr, left, right):
    mid = (left + right)/2
    if arr[right] < arr[left]:
        Swap(arr, left, right)        
    if arr[mid] < arr[left]:
        Swap(arr, mid, left)
    if arr[right] < arr[mid]:
        Swap(arr, right, mid)
    return mid

# Generic Swap for manipulating list data.
def Swap(arr, left, right):
    temp = arr[left]
    arr[left] = arr[right]
    arr[right] = temp    

Answer 4

common/ vanilla 快速排序选择最右边的元素作为枢轴。这导致它在许多情况下表现出 O(N²) 的病理性能。特别是排序和反向排序的集合。在这两种情况下，最右边的元素是最糟糕的可能选择作为枢轴的元素。对我来说，在分区中间理想地认为支点。分区应该将带有枢轴的数据分成两个部分，一个低部分和一个高部分。低部分低于枢轴，高部分更高。

三中枢轴选择的中位数：

• 选择最左边、中间和最右边的元素
• 将它们排序到左分区、枢轴和右分区。以与常规快速排序相同的方式使用枢轴。

排序/反向排序输入的常见病理 O(N²) 会由此减轻。为 3 的中位数创建病理输入仍然很容易。但这是一种人为的恶意使用。不是自然排序。

随机枢轴：

• 选择一个随机枢轴。将此用作常规枢轴元素。

如果是随机的，这不会表现出病态的 O(N²) 行为。对于通用排序，随机主元通常很可能是计算密集型的，因此是不可取的。如果它不是随机的（即 srand(0); , rand() ，则是可预测的并且容易受到与上述相同的 O(N²) 漏洞的攻击。

请注意，随机枢轴不会从选择多个元素中受益。主要是因为中位数的影响已经是固有的，一个随机值比两个元素的排序计算量更大。

Answer 5

想简单... Python 示例....

def large(a,b): #找出两个数中较大的一个...
    如果 a > b：
        返回一个
    别的：
        返回 b

def maximum(a,b,c): #求三个数中最大的...
    返回更大（a，更大（b，c））

def中值（a，b，c）：#跳舞吧！
    x = 最大（a，b，c）
    如果 x == a：
        返回更大（b，c）
    如果 x == b：
        返回更大（a，c）
    别的：
        返回更大（a，b）