python数据结构与算法 35 快速排序

python数据结构与算法 35 快速排序

快速排序

快速排序也使用了分而治之的策略来提高性能，而且不需要额外的内存，但是这么做的代价就是，列表不是对半切分的，因而，性能上就有所下降。

快速排序选择一个数值，一般称为“轴点”，虽然有很多选取轴点的方法，我们还是简单地把列表中第一个元素做为轴点了。轴点的作用是帮助把列表分为两个部分。列表完成后，轴点所在的位置叫做“切分点”，从这一点上把列表分成两部分供后续调用。

图12所示，54将作为轴点。这个例子我们已经排过多次了，我们知道54在排好序后将处于现在31的位置上。找到轴点以后，把列表中其他元素，按比轴点大或比轴点小的方法，分成两部分。

图12 快速排序的第一个轴点

切分开始于定位两个位置标志……就叫做“左标”和“右标”好了……分别位于剩余列表元素的开始和结束处（图13的1位和8位）。切分的目标，是把相对于轴点来说，位置错误的元素移动在正确的位置上，同时左标和右标也将在“切分点”上相聚。

vcHLOTO6zTIwo6zP1tTasNHBvbj21KrL2L27u7ujrMi7uvPW2Li0yc/K9rn9s8yhozwvcD4KPHA+tbE8Y29kZT5yaWdodG1hcms8L2NvZGU+INCh09ogPGNvZGU+bGVmdG1hcms8L2NvZGU+yrGjrM2j1rmho9XiyrE8Y29kZT5yaWdodG1hcms8L2NvZGU+ILPJzqrH0LfWteOjrNbhteMmIzIwNTQwO9Prx9C31rXjtcQmIzIwNTQwO727u7ujrNbhtePS0b6t1dK1vc671sOjqM28MTSjqaGjwe3N4qOsy/nT0MfQt9a149fzsd+1xNSqy9i2vNCh09rW4bXjo6zL+dPQ09Kx37XE1KrL2LTz09rW4bXjo6zV4sqxwdCx7bTTx9C31rXjtKa31rPJwb249tfTse2jrMq508O13bnptffTw9bYuLS/7MvZxcXQ8rn9s8yhozwvcD4KPGltZyBzcmM9"http://www.2cto.com/uploadfile/Collfiles/20140504/20140504090159242.jpg" alt="\">
图14 完成切分

下面是实现quickSort的函数。它调用了一个递归函数quickSortHelper. quickSortHelper.的基点和归并排序是一样的，如果列表的长度小于等于1，它就是有序的，如果大于1，它就要被切分并且递归排序。Partition 函数完成前面提到过的切分过程。

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

def quickSortHelper(alist,first,last):
   if first= 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

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

为了分析快速排序函数性能，要注意到一个长度为n的列表，如果切分点总是在列表的中间，那么就是要logn 次切分。为了找到切分点，n个元素都要与轴点作一次比较，结果需要nlogn.另外，也不需要象归并排序一样消耗额外的内存。不幸的是，在最怀的情况下，切分点不在中间，而是偏左或偏右，生成很不均匀的子表，这种情况下，生成的子表是一个0个元素，一个n-1个元素，然后再切分，却生成一个子表是0个元素，另一个是n-2个元素等等。结果需要的开销就是O(n²)。

前面我们提到过有不同的方式来选择轴点，尤其是，我们可以使用一种叫做“三数取中”的技术，以减轻不均匀切分的可能性。这种方法从列表的第一个，中间的一个，最后的一个元素三个数中，取中间值。象上面的例子中，三数是54，77和20，，那么选中54作为轴点。这种思想的来源，是认为第一个元素可能它的大小并不在中间的位置，但是三个数的中间值就比较靠近中间。这种方法特别适合那些开始时已经部分有序的列表。这个轴点值的选择方法留作练习。