快速排序需要提供三个参数:待排序序列、序列最小下标值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]
: