实现三数取中法的快速排序

Question

我在《用算法和数据结构解决问题》这本书里发现了快速排序算法，作者是布拉德·米勒和大卫·拉纳姆（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