Python：中位数为 3 的快速排序

Question

我正在尝试更改此快速排序代码以使用采用 "median of three" 的枢轴。

def quickSort(L, ascending = True): 
    quicksorthelp(L, 0, len(L), ascending)


def quicksorthelp(L, low, high, ascending = True): 
    result = 0
    if low < high: 
        pivot_location, result = Partition(L, low, high, ascending)  
        result += quicksorthelp(L, low, pivot_location, ascending)  
        result += quicksorthelp(L, pivot_location + 1, high, ascending)
    return result


def Partition(L, low, high, ascending = True):
    print('Quicksort, Parameter L:')
    print(L)
    result = 0 
    pivot, pidx = median_of_three(L, low, high)
    L[low], L[pidx] = L[pidx], L[low]
    i = low + 1
    for j in range(low+1, high, 1):
        result += 1
        if (ascending and L[j] < pivot) or (not ascending and L[j] > pivot):
            L[i], L[j] = L[j], L[i]  
            i += 1
    L[low], L[i-1] = L[i-1], L[low] 
    return i - 1, result

liste1 = list([3.14159, 1./127, 2.718, 1.618, -23., 3.14159])

quickSort(liste1, False)  # descending order
print('sorted:')
print(liste1)

但我不太确定该怎么做。中位数必须是列表的第一个、中间和最后一个元素的中位数。如果列表的元素个数为偶数，则中间成为前半部分的最后一个元素。

这是我的中值函数：

def median_of_three(L, low, high):
    mid = (low+high-1)//2
    a = L[low]
    b = L[mid]
    c = L[high-1]
    if a <= b <= c:
        return b, mid
    if c <= b <= a:
        return b, mid
    if a <= c <= b:
        return c, high-1
    if b <= c <= a:
        return c, high-1
    return a, low

Answer 1

我们先实现三个数的三中位数，一个独立的函数。我们可以通过对三个元素的列表进行排序，然后 return 第二个元素来做到这一点，例如：

def median_of_three(a, b, c):
    return <b>sorted([a, b, c])[1]</b>

现在对于范围 low .. high（包括 low，排除 high），我们应该确定哪些元素是我们应该构造三个中值的元素：

第一个元素：L[low],
最后一个元素L[high-1]，并且
中间元素（如果有两个，取第一个）L[(low+high-1)//2].

所以现在我们只需要将分区函数打补丁为：

def Partition(L, low, high, ascending = True):
    print('Quicksort, Parameter L:')
    print(L)
    result = 0 
    pivot = <b>median_of_three(L[low], L[(low+high-1)//2], L[high-1])</b>
    i = low + 1  
    for j in range(low + 1, high, 1): 
        result += 1
        if (ascending and L[j] < pivot) or (not ascending and L[j] > pivot):
            L[i], L[j] = L[j], L[i]  
            i += 1  
    L[low], L[i-1] = L[i-1], L[low] 
    return i - 1, result

编辑：确定三个元素的中位数。

三个元素的中位数是位于其他两个值中间的元素。所以如果 a <= b <= c，那么 b 就是中位数。

所以我们需要确定元素的排列顺序，这样才能确定中间的元素。喜欢：

def median_of_three(a, b, c):
    if a <= b and b <= c:
        return b
    if c <= b and b <= a:
        return b
    if a <= c and c <= b:
        return c
    if b <= c and c <= a:
        return c
    return a

所以现在我们已经用四个 if 个案例定义了三个的中位数。

EDIT2：这个还是有问题。执行枢轴后，将元素 L[i-1] 与原始代码中的 L[low] 交换（枢轴的位置）。但这当然不再有效：因为枢轴现在可以位于三个维度中的任何一个。因此，我们需要使 median_of_three(..) 更智能：它不仅应该 return 枢轴元素，还应该 return 枢轴的位置：

def median_of_three(L, low, high):
    mid = (low+high-1)//2
    a = L[low]
    b = L[mid]
    c = L[high-1]
    if a <= b <= c:
        return b, mid
    if c <= b <= a:
        return b, mid
    if a <= c <= b:
        return c, high-1
    if b <= c <= a:
        return c, high-1
    return a, low

现在我们可以解决这个问题：

def Partition(L, low, high, ascending = True):
    print('Quicksort, Parameter L:')
    print(L)
    result = 0 
    pivot<b>, pidx</b> = <b>median_of_three(L, low, high)</b>
    i = low + <b>(low == pidx)</b>
    for j in range(low, high, 1):
        <b>if j == pidx:
            continue</b>
        result += 1
        if (ascending and L[j] < pivot) or (not ascending and L[j] > pivot):
            L[i], L[j] = L[j], L[i]  
            i += 1 + <b>(i+1 == pidx)</b>
    L[<b>pidx</b>], L[i-1] = L[i-1], L[<b>pidx</b>] 
    return i - 1, result

EDIT3：清理它。

虽然上面看起来可行，但它相当复杂：我们需要让 i 和 j "skip" 枢轴的位置。

如果我们先将枢轴移动到子列表的前面（所以到 low 索引），可能会更简单：

def Partition(L, low, high, ascending = True):
    print('Quicksort, Parameter L:')
    print(L)
    result = 0 
    pivot, pidx = median_of_three(L, low, high)
    <b>L[low], L[pidx] = L[pidx], L[low]</b>
    i = low + <b>1</b>
    for j in range(low<b>+1</b>, high, 1):
        result += 1
        if (ascending and L[j] < pivot) or (not ascending and L[j] > pivot):
            L[i], L[j] = L[j], L[i]  
            i += 1
    L[<b>low</b>], L[i-1] = L[i-1], L[<b>low</b>] 
    return i - 1, result

Answer 2

在 "median of three" 版本的快速排序中，您不仅要找到中位数以将其用作基准，还想将最大值和最小值放在它们的位置，因此一些旋转已经完成。换句话说，您想在这三个地方对这三个项目进行排序。（有些变体不希望它们以通常的方式排序，但我会在这里为您坚持一个更容易理解的版本。）

您可能不想在函数中执行此操作，因为函数调用在 Python 中相当昂贵，而且此特定功能的用途并不广泛。所以你可以做一些这样的代码。假设您要排序的三个值位于索引 i、j 和 k 以及 i < j < k 中。在实践中，您可能会使用 low、low + 1 和 high，但您可以根据需要进行这些更改。

if L(i) > L(j):
    L(i), L(j) = L(j), L(i)
if L(i) > L(k):
    L(i), L(k) = L(k), L(i)
if L(j) > L(k):
    L(j), L(k) = L(k), L(j)

可以进行一些优化。例如，您可能希望在数据透视过程中使用中值，因此您可以更改代码以将 L(j) 的最终值存储在一个简单的变量中，从而减少数组查找。请注意，一般情况下，您不能在少于三个比较的情况下执行此操作——您不能将其减少为两个比较，但在某些特殊情况下您可以这样做。

Python：中位数为 3 的快速排序

Python: Quicksort with median of three

python

sorting

pivot

quicksort

median