如何改进 python 中的快速排序枢轴选择？

Question

我最初只使用

给出的一个随机主元

pivots = random.randrange(l,r)

这里 l 和 r 将是定义我的范围的整数

我想通过选择三个随机枢轴的中值来大大增加我的枢轴成为一个好的枢轴的可能性，从而缩短运行时间。下面是我使用的代码，它使我的运行时间增加了 20%-30%。

rr = random.randrange
pivots = [ rr(l,r) for i in range(3) ]
pivots.sort()

如何更快地实施上述内容？

编辑：下面添加了完整代码

import random

def quicksort(array, l=0, r=-1):
    # array is list to sort, array is going to be passed by reference, this is new to me, try not to suck
    # l is the left bound of the array to be acte on
    # r is the right bound of the array to act on

    if r == -1:
        r = len(array)

    # base case
    if r-l <= 1:
        return

    # pick the median of 3 possible pivots
    #pivots = [ random.randrange(l,r) for i in range(3) ]
    rr = random.randrange
    pivots = [ rr(l,r) for i in range(3) ]
    pivots.sort()

    i = l+1 # Barrier between below and above piviot, first higher element
    array[l], array[pivots[1]] = array[pivots[1]], array[l]

    for j in range(l+1,r):
        if array[j] < array[l]:
            array[i], array[j] = array[j], array[i]
            i = i+1

    array[l], array[i-1] = array[i-1], array[l]

    quicksort(array, l, i-1)
    quicksort(array, i, r)

    return array

编辑 2：这是更正后的代码。选择 3 个枢轴的算法存在错误

import random

def quicksort(array, l=0, r=-1):
    # array is list to sort, array is going to be passed by reference, this is new to me, try not to suck
    # l is the left bound of the array to be acte on
    # r is the right bound of the array to act on

    if r == -1:
        r = len(array)

    # base case
    if r-l <= 1:
        return

    # pick the median of 3 possible pivots
    mid = int((l+r)*0.5)
    pivot = 0
    #pivots = [ l, mid, r-1]
    if array[l] > array[mid]:
        if array[r-1]> array[l]:
            pivot = l
        elif array[mid] > array[r-1]:
            pivot = mid
    else:
        if array[r-1] > array[mid]:
            pivot = mid
        else:
            pivot = r-1

    i = l+1 # Barrier between below and above piviot, first higher element
    array[l], array[pivot] = array[pivot], array[l]

    for j in range(l+1,r):
        if array[j] < array[l]:
            array[i], array[j] = array[j], array[i]
            i = i+1

    array[l], array[i-1] = array[i-1], array[l]

    quicksort(array, l, i-1)
    quicksort(array, i, r)

    return array

Answer 1

虽然随机选择有时会优于它，但仍然值得研究 median-of-medians 枢轴选择算法（以及一般的排名选择），该算法运行时间为 O(n)。它与您目前正在做的事情并不太远，但它背后有一个更有力的保证，它会选择一个 "good" 轴心，而不是仅仅取三个随机数的中位数。

Answer 2

你可以这样选择支点：

alen = len(array)
pivots = [[array[0],0], [array[alen//2],alen//2], [array[alen-1],alen-1]]]
pivots.sort(key=lambda tup: tup[0]) #it orders for the first element of the tupla
pivot = pivots[1][1]

示例：

如何改进 python 中的快速排序枢轴选择？

How do I improve my quick sort pivot selection in python?

python

pivot

quicksort