Quicksort

Question

def quicksort(L, low, high):
    total = 0
    if low < high:
        pivot_location, total = Partition(L, low, high)
        total += quicksort(L,low,pivot_location)
        total += quicksort(L,pivot_location + 1, high)
    return total 

def Partition(L, low, high):
    print(L)
    #print(high)
    total = 0
    if (high - low) % 2 == 0:
        middle = (high - low) // 2 - 1
    else:
        middle = ((high - low) // 2) + low
    print(L[low])
    print(L[high - 1])
    print(L[middle])
    numbers = []
    numbers.append(L[low])
    numbers.append(L[middle])
    numbers.append(L[high - 1])
    if L[low] > L[middle] and L[low] < L[high - 1]:
        pivot = L[low]
    elif L[low] >L[high -1] and L[low] < L[middle]:
        pivot = L[low]
    elif L[middle] < L[low] and L[middle] > L[high -1]:
        temp = L[low]
        L[low] = L[middle]
        L[middle] = temp
        pivot = L[low]
    elif L[middle] < L[high - 1] and L[middle] > L[low]:
        temp = L[low]
        L[low] = L[middle]
        L[middle] = temp
        pivot = L[low]
    elif L[high - 1] < L[low] and L[high - 1] > L[middle]:
        temp = L[low]
        L[low] = L[high - 1]
        L[high - 1] = temp
        pivot = L[low]
    else:
        temp = L[low]
        L[low] = L[high - 1]
        L[high - 1] = temp
        pivot = L[low]
    print(pivot)
    i = low + 1
    for j in range(low + 1,high,1):
        total += 1
        if L[j] < pivot:
            temp = L[j]
            L[j] = L[i]
            L[i] = temp
            i += 1
    temp = L[low]
    L[low] = L[i -1]
    L[i - 1] = temp
    #print(L)
    return i - 1,total  

c = [2148,9058,7742,3153,6324,609,7628,5469,7017,504]
print(quicksort(c, 0, len(c)))  
print(c)

我已经用这种方式实现了快速排序。我尝试将第一个元素用作枢轴，将最后一个元素用作枢轴，并且效果很好。但是我无法弄清楚如何选择三个元素的中位数作为枢轴：第一，中间，最后。关于如何在每个递归调用中选择中间元素的任何帮助。请注意，我想将整个数组作为参数传递给每个递归调用，因为我不想使用任何额外的内存。

Answer 1

另一种将 3 个元素的中位数放置到位的方法：

def compareswap(L,a,b):
    L[a], L[b] = min(L[a],L[b]),max(L[a],L[b])

def medianfirst(L,a,b,c):
    compareswap(L,b,a) # L[b]<=L[a]
    compareswap(L,b,c) # L[b]<=L[c] i.e L[b] smallest
    compareswap(L,a,c) # L[a]<=L[c] i.e L[c] largest

现在在 Partition 中使用 medianfirst 与：

    medianfirst(L,low,middle,high-1)
    pivot = L[low]

而不是大 if-elif-else 块。

----更新----

（固定middle在偶数元素区间选择第一个）为方便起见，修改后的 Partition:

def Partition(L, low, high):
    print(L)
    total = 0
    middle = (low+high-1)//2
    medianfirst(L,low,middle,high-1)
    pivot = L[low]
    i = low + 1
    for j in range(low + 1,high,1):
        total += 1
        if 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,total

Answer 2

def partition_median(L, low, high):
    left = L[low]
    right = L[high-1]
    length = high - low
    if length % 2 == 0:
        middle = L[int(low + length/2 - 1)]
    else:
        middle = L[int(low + length/2)]
    pivot = median(left, right, middle)
    pivotindex = L.index(pivot) #works only for unique values
    L[pivotindex] = L[low]
    L[low] = pivot
    i = low + 1
    for j in range(low + 1, high):
        if L[j] < pivot:
            temp = L[j]
            L[j] = L[i]
            L[i] = temp
            i += 1
    leftend = L[low]
    L[low] = L[i-1]
    L[i-1] = leftend
    return i - 1

好吧，多亏了我得到的帮助和更多的思考，我设法用上面的分区子程序实现了我想要的东西！

Quicksort - 三个选择的枢轴的媒体

Quicksort - Media of Three chosen pivot

python