快速排序的Python实现

先来看一个 我更想称之为伪快排的快排代码：

defquick_sort(array):iflen(array)<2:returnarrayelse:pivot=array[0]less_than_pivot=[xforx inarrayifx<=pivot]more_than_pivot=[xforx inarrayifx>pivot]returnquick_sort(less_than_pivot)+[pivot]+quick_sort(more_than_pivot)

这段代码最关键的是pivot这个参数，这段代码里取序列的第一个元素，然后以这个元素为分组的基准，利用列表解析式使得它左边的值都比它小，右边的值都比它大。然后再分别对这些序列进行递归排序。

这段代码虽然短小利于理解，但是其效率很低，主要体现在以下方面：

• 分组基准的选取过于随便，不一定可以取到列表的中间值
• 空间复杂度大，使用了两个列表解析式，而且每次选取进行比较时需要遍历整个序列。
• 若序列长度过于小(比如只有几个元素)，快排效率就不如插入排序了。
• 递归影响性能，最好进行优化。

下面用Python写一个C风格的快排(这里可以体会到快排的精髓)：

defquick_sort(L):returnq_sort(L,0,len(L)-1)defq_sort(L,left,right):ifleft<right:pivot=Partition(L,left,right)q_sort(L,left,pivot-1)q_sort(L,pivot+1,right)returnL

defPartition(L,left,right):pivotkey=L[left]whileleft<right:whileleft<rightand L[right]>=pivotkey:right-=1L[left]=L[right]whileleft<rightand L[left]<=pivotkey:left+=1L[right]=L[left]L[left]=pivotkeyreturnleftL=[5,9,1,11,6,7,2,4]printquick_sort(L)

快速排序需要提供三个参数：待排序序列、序列最小下标值left、序列最大下标值right。让用户提供这三个参数很麻烦。这里写个函数进行封装：

defquick_sort(L):returnq_sort(L,0,len(L)-1)

下面看一下q_sort函数：

defq_sort(L,left,right):ifleft<right:pivot=Partition(L,left,right)q_sort(L,left,pivot-1)q_sort(L,pivot+1,right)returnL

这个函数的核心是pivot = Partition(L, left, right)，在执行它之前，列表的值为[5, 9, 1, 11, 6, 7, 2, 4]，而Partition函数做的事情是找到一个分组标准，然后进行分组，让它左边的值比它小，右边的值比它大。
在经过Partition函数分组后，列表变为[4, 2, 1, 5, 6, 7, 11, 9]，并把5的下标值(也就是3)返回给pivot，此时列表变成两个小列表[4, 2, 1]和[5, 6, 7, 11, 9] ，之后调用q_sort，就是调用q_sort(L,0, 2)和q_sort(L, 4 ,7)，对其进行Partition操作，直到整个列表有序为止。

下面看看关键的Partition函数是如何做的：

defPartition(L,left,right):pivotkey=L[left]whileleft<right:whileleft<rightand L[right]>=pivotkey:right-=1L[left]=L[right]whileleft<rightand L[left]<=pivotkey:left+=1L[right]=L[left]L[left]=pivotkeyreturnleft

以一趟排序为例[5, 9, 1, 11, 6, 7, 2, 4]：

• 开始排序时，left=0，right=7，首先用表的第一个下标值作为 分组关键字pivot，

                                                                 第一趟排序过程