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

本文介绍了Python:中位数为三的快速排序的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试更改此快速排序代码以使用采用三的中位数"的数据透视.

I'm trying to change this quicksort code to work with a pivot that takes a "median of three" instead.

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)

但我不确定如何做到这一点.中位数必须是列表的第一个、中间和最后一个元素的中位数.如果列表有偶数个元素，则中间成为前半部分的最后一个元素.

But I'm not really sure how to do that. The median has to be the median of the first, middle and last element of a list. If the list has an even number of elements, middle becomes the last element of the first half.

这是我的中值函数:

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

推荐答案

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

Let us first implement the median-of-three for three numbers, so an independent function. We can do that by sorting the list of three elements, and then return the second element, like:

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

现在对于范围 low .. high(包括 low，排除 high)，我们应该确定元素的用途我们应该构造三个的中位数:

Now for a range low .. high (with low included, and high excluded), we should determine what the elements are for which we should construct the median of three:

第一个元素:L[low],

最后一个元素L[high-1]，和

中间元素(如果有两个，取第一个)L[(low+high-1)//2].

所以现在我们只需要将分区函数修补为:

So now we only need to patch the partitioning function to:

def Partition(L, low, high, ascending = True): print('Quicksort, Parameter L:') print(L) result = 0 pivot = median_of_three(L[low], L[(low+high-1)//2], L[high-1]) 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

编辑:确定三个元素的中值.

EDIT: determining the median of three elements.

三个元素的中位数是位于其他两个值中间的元素.因此，如果 a <= b <= c，则 b 是中位数.

The median of three elements is the element that is in the middle of the two other values. So in case a <= b <= c, then b is the median.

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

So we need to determine in what order the elements are, such that we can determine the element in the middle. Like:

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 情况定义了三个的中位数.

So now we have defined the median of three with four if cases.

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

EDIT2: There is still a problem with this. After you perform a pivot, you swap the element L[i-1] with L[low] in your original code (the location of the pivot). But this of course does not work anymore: since the pivot now can be located at any of the three dimensions. Therfore we need to make the median_of_three(..) smarter: not only should it return the pivot element, but the location of that pivot as well:

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

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

Now we can solve this problem with:

def Partition(L, low, high, ascending = True): print('Quicksort, Parameter L:') print(L) result = 0 pivot, pidx = median_of_three(L, low, high) i = low + (low == pidx) for j in range(low, high, 1): if j == pidx: continue 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 + (i+1 == pidx) L[pidx], L[i-1] = L[i-1], L[pidx] return i - 1, result

EDIT3:清理它.

虽然上面的方法看起来可行，但它相当复杂:我们需要让 i 和 j 跳过"枢轴的位置.

Although the above seems to work, it is quite complicated: we need to let i and j "skip" the location of the pivot.

如果我们首先将主元移动到子列表的前面(因此移动到 low 索引)可能更简单:

It is probably simpler if we first move the pivot to the front of the sublist (so to the low index):

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