python - 实现中位数为三的快速排序

Question

我在 Brad Miller 和 David Ranum 所著的“用算法和数据结构解决问题”中偶然发现了快速排序算法 ( http://interactivepython.org/runestone/static/pythonds/SortSearch/sorting.html#the-quick-sort )。

此处提供的快速排序算法将列表中的第一个值作为主值。练习是修改程序以选择枢轴值作为三的中位数。这是原始脚本:

def quickSort(alist):
   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
   if first<last:

       splitpoint = partition(alist,first,last)

       quickSortHelper(alist,first,splitpoint-1)
       quickSortHelper(alist,splitpoint+1,last)


def partition(alist,first,last):
   pivotvalue = alist[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark <= rightmark and \
               alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and \
               rightmark >= leftmark:
           rightmark = rightmark -1

       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp


   return rightmark

我对其进行了一些修改，首先添加了 median() 函数:

def median(data):
    sd = sorted(data)
    N = len(data) - 1
    a = sd[N // 2]
    b = sd[(N + 1) // 2]
    return (a+b) // 2

然后，在partition()函数中，将pivotvalue修改为:

pivotvalue = median([alist[0]] + [alist[len(alist)-1]] + [alist[len(alist)//2]])

并将 leftmark 更改为以索引 0 开头，而不是 1:

leftmark = first

而不是:

leftmark = first+1

然后更改了最终done == True时执行的步骤，以正确交换rightmark和pivot值:

temp = pivotvalue
alist[alist.index(pivotvalue)] = alist[rightmark]
alist[rightmark] = temp

但是当调用时:

alist = [77,26,93,17,54,31,44,55,20]
quickSort(alist)
print(alist)

我得到:

Traceback (most recent call last):
  File "/home/reloader/Templates/Exercises/quick_sort.py", line 52, in <module>
    quickSort(alist)
  File "/home/reloader/Templates/Exercises/quick_sort.py", line 9, in quickSort
    quickSortHelper(alist,0,len(alist)-1)
  File "/home/reloader/Templates/Exercises/quick_sort.py", line 17, in quickSortHelper
    quickSortHelper(alist,splitpoint+1,last)
  File "/home/reloader/Templates/Exercises/quick_sort.py", line 17, in quickSortHelper
    quickSortHelper(alist,splitpoint+1,last)
  File "/home/reloader/Templates/Exercises/quick_sort.py", line 17, in quickSortHelper
    quickSortHelper(alist,splitpoint+1,last)
  File "/home/reloader/Templates/Exercises/quick_sort.py", line 17, in quickSortHelper
    quickSortHelper(alist,splitpoint+1,last)
  File "/home/reloader/Templates/Exercises/quick_sort.py", line 17, in quickSortHelper
    quickSortHelper(alist,splitpoint+1,last)
  File "/home/reloader/Templates/Exercises/quick_sort.py", line 17, in quickSortHelper
  .......
  RuntimeError: maximum recursion depth exceeded in comparison

由于我发现这个算法有点复杂(并且执行的步骤有点太多)，我真的不知道要更改什么才能使其正常工作，而且我所做的破坏了我的修改。我只是将枢轴值设置为列表中间的值。其他我目前看不到的东西是否也应该修改？

谢谢。

编辑:

如果我将 leftmark 的初始值保留为 firstmark + 1 (即列表的索引 1)，我不会收到无限递归错误，但列表也未正确排序:

[55, 26, 31, 44, 17, 77, 54, 20, 93]

Answer 1

您必须从正在分区的子数组中选择中位数:

替换这个:

pivotvalue = alist[first]

与

pivotindex = median(alist, first, last, (first + last) // 2)
alist[first], alist[pivotindex] = alist[pivotindex], alist[first]
pivotvalue = alist[first]

中值查找器不必如此复杂。

def median(a, i, j, k):
  if a[i] < a[j]:
    return i if a[k] < a[i] else k if a[k] < a[j] else j
  else:
    return j if a[k] < a[j] else k if a[k] < a[i] else i