Python:中位数为三的快速排序

Question

我正在尝试更改此快速排序代码，以使用采用“三的中位数”的枢轴。

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)

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

这是我的中值函数:

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

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

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

现在范围 low .. high (包含low，排除high)，我们应该确定我们应该构建三个中位数的元素是什么:

1. 第一个元素:L[low] ,
2. 最后一个元素 L[high-1] ，并且
3. 中间元素(如果有两个，则取第一个)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(..)更聪明:它不仅应该返回枢轴元素，还应该返回该枢轴的位置:

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 “跳过”枢轴的位置。

如果我们首先将枢轴移动到子列表的前面(因此移动到 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