中间值为3的快速排序功能不起作用

Question

我正试图在python中实现一个中值为三的快速排序算法，但无法弄清楚哪里出了问题以及为什么它不起作用

from statistics import median
def Swap(arr, posA, posB):
arr[posA], arr[posB] = arr[posB], arr[posA]
def Median(array):
medianValue = median([array[0], array[int(len(array)/2)], array[-1]])
return array.index(medianValue)
def Partition(array, start, end):
pivot = array[end]
i = start-1
for j in range(start, end):
if array[j] <= pivot:
i += 1
Swap(array, i, j)
Swap(array, i+1, end)
return i + 1
def Quicksort(array, startInd, endInd):
if startInd < endInd:
medianIndex = Median(array)
Swap(array, medianIndex, endInd)
pivot  = Partition(array, startInd, endInd)
Quicksort(array, startInd, pivot  - 1)
Quicksort(array, pivot  + 1, endInd)

感谢您的帮助：(

Answer 1

问题是，你得到的中位数是基于整个数组，而不是正在处理的子部分。一个可能的解决方案是：

将中值函数更改为：

def Median(array, firstVal, middleVal, endVal):
if (firstVal - middleVal) * (endVal - firstVal) >= 0:
medianValue =  firstVal
elif (middleVal - firstVal) * (endVal - middleVal) >= 0:
medianValue = middleVal
else:
medianValue = endVal
return array.index(medianValue)

然后将您的快速分拣功能更改为

def Quicksort(array, startInd, endInd):
if startInd < endInd:
# get median
middleVal = (endInd + startInd) // 2
medianIndex = Median(array, array[startInd], array[middleVal],
array[endInd])
#
Swap(array, medianIndex, endInd)
pivot  = Partition(array, startInd, endInd)
Quicksort(array, startInd, pivot  - 1)
Quicksort(array, pivot  + 1, endInd)