查找与排序：快速排序
快速排序
我们现在再看看快速排序。
快速排序采用的是分而治之的原则，基本思路是，随便先选择一个数比如第一个数，以它为基准，按照一定的办法把比它小的放到它前面，比它大的放到它后面，这样整个数据序列就整体分成了小和大两堆，然后在每一堆里面继续这个操作。
我们看一个例子，假定手头有这么一个数字序列：
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
72 |
6 |
57 |
88 |
60 |
42 |
83 |
73 |
48 |
85 |
我们先把第一个数72拿出来，以它为基准去比对并分成两堆。
pivot = 72
拿出来之后，数字序列就出来了一个空。形如下：
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
6 |
57 |
88 |
60 |
42 |
83 |
73 |
48 |
85 |
我们现在就要去在序列中找一个合适的数字填空。按照这个办法找，我们拿这个基准数是从最左边拿的，现在空也在最左边，我们就从最右边开始找数。
最右边位置9的数是85，比基准数72要大，我们不用管它，位置减1，往左移动一格，得到位置8的数，是48，比72小，我们就把这个数拿出来填空。形如：
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
48 |
6 |
57 |
88 |
60 |
42 |
83 |
73 |
85 |
这个时候，空就换到了位置8了。我们再反向从左往右找，从位置1开始（因为位置0已经是填好空了，不用管了），这个数是6，比72小，不用管，位置加1，往右移动一格，得到位置2的数，是57，还是比72小，不用管，位置加1，往右移动一格，得到位置3的数，是88，比72大，就把这个数拿出来填空，形如：
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
48 |
6 |
57 |
60 |
42 |
83 |
73 |
88 |
85 |
这个时候，空就换到了位置3了。我们再反向从右往左找，从位置7开始（因为位置8已经是填好空了，不用管了），这个数是73，比72大，不用管，位置减1，往左移动一格，得到位置6的数，是83，比72大，不用管，位置减1，往左移动一格，得到位置5的数，是42，比72小，就把这个数拿出来填空，形如：
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
48 |
6 |
57 |
42 |
60 |
83 |
73 |
88 |
85 |
这个时候，空就换到了位置5了。我们再反向从左往右找，从位置4开始（因为位置3已经是填好空了，不用管了），这个数是60，比72小，不用管位置加1，往右移动一格，位置为5，碰到了空格，于是这一遍就结束了。我们把72放到位置5。形如：
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
48 |
6 |
57 |
42 |
60 |
72 |
83 |
73 |
88 |
85 |
到此，整个数列，位置5左边的都比72小，右边的都比72大，所以呢，成了局部有序的了。我们接下来就按照同样的办法把位置0-4的子序列排序，把位置6-9的子序列排序。
0 |
1 |
2 |
3 |
4 |
48 |
6 |
57 |
42 |
60 |
pivot=48
拿出来48，有了空，形如：
0 |
1 |
2 |
3 |
4 |
6 |
57 |
42 |
60 |
从右边开始比对，到了位置3，数为42，比48小，填空，形如：
0 |
1 |
2 |
3 |
4 |
42 |
6 |
57 |
60 |
再从左边开始比对，到了位置2，数为57，比48大，填空，形如：
0 |
1 |
2 |
3 |
4 |
42 |
6 |
48 |
57 |
60 |
就按照这个递归的办法这么一步一步的排序。
从程序实现上，我们是按照递归一遍一遍执行的，对每一遍里面来讲，我们需要三个标记，一个标记空的位置，一个标记左限，一个标记右限。
我们先看怎么实现第一遍：
arr[pivotIndex],arr[left]=arr[left],arr[pivotIndex]
def partition(arr,start,end):
pivotIndex = start #初始空，在最左边
pivot = arr[start] #基准值初始化为最左边的数
left = start+1
right = end
while right>=left:
while right>=left and arr[right]>=pivot: #从右开始逐个比对，大就继续比对
right-=1
if right>=left: #右边找到了一个小于基准值的，交换填空
swap(arr,pivotIndex,right)
pivotIndex=right
right-=1
while left<=right and arr[left]<=pivot:#从左开始逐个比对，小就继续比对
left+=1
if left<=right:#左边找到了一个大于基准值的，交换填空
swap(arr,pivotIndex,left)
pivotIndex=left
left+=1
return pivotIndex
程序对一个列表的某一段范围的数列按照某个基准值进行分割，解释已经写到代码里面了。交换数据的语句：
arr[pivotIndex],arr[left]=arr[left],arr[pivotIndex]
这个是Python比较特殊的表达。
测试一下：
a = [72,6,57,88,60,42,83,73,48,85]
i=partition(a,0,len(a)-1)
print(i)
print(a)
运行结果为：
5
[48, 6, 57, 42, 60, 72, 83, 73, 88, 85]
你可以一步步跟踪，看这一遍是怎么填空的。
现在有了某一遍的程序，在外面再套一个递归，把过程演练完：
def quicksort(arr,start,end):
index = partition(arr, start, end)
if index > start:
quicksort(arr, start, index - 1)
if index < end:
quicksort(arr, index + 1, end)
return arr
测试一下：
a = [72,6,57,88,60,42,83,73,48,85]
print(quicksort(a,0,len(a)-1))
运行结果为：
[6, 42, 48, 57, 60, 72, 73, 83, 85, 88]
快速排序的一次划分算法从两头交替搜索，直到low和high重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。理想的情况下，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。但是如果运气不好，最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素（也就是序列本来就是基本有序的），那就退化成O(n2)。
平均而言，快速排序，确实性能提高了很多。这个算法被誉为二十世纪七大算法之一。
快速排序由英国著名科学家Hoare发明。他是一个谦逊的绅士，曾经说自己一生唯一有意义的工作就是这个算法。
点击“阅读原文”,可进入原创书籍，阅读目录