我正在尝试更改此快速排序代码以使用采用三的中位数"的数据透视.
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:
所以现在我们只需要将分区函数修补为:
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, resultEDIT3:清理它.
虽然上面的方法看起来可行,但它相当复杂:我们需要让 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更多推荐
Python:中位数为三的快速排序
发布评论