递归排序算法快速排序的实现过程

快速排序(Insertion Sort)也是一种递归排序算法。

快速排序原理：先以列表中的任意一个数为基准(一般选头或尾)，将列表分为左、右两个子列表。

左子列表的数要比基准数小，右子列表的数要比基准数大。然后继续把左子列表和右子列表按同样的方法继续分解、比较，直到分无可分。最后将左子列表(比基准数小)+基准数+右子列表(比基准数大)连接起来得到一个有序数列。

以数列[3,5,8,1,2,9,4,7,6]为例，最初的数列顺序如上图所示。

第一次分组：以最后一个元素6为基准将数列分成两组。分别从左右两端遍历数列，比6小的分在左边，比6大的分在右边。先从左向右遍历，当遇到比6大的元素时将该元素放到右边。同理从右向左遍历时，遇到比6小的元素放到左边。当全部元素被遍历之后，将左边数列，元素6，右边数列按顺序拼接成新的数组，此时元素6的位置固定。

递归处理左边子数列：以最后一个元素2为基准，比2小的分在左边子数列中，比2大的分在右边子数列中经过一轮分组后，元素2的位置已经固定，接下来继续递归的调用上述过程……

递归处理右边子数列：以最后一个元素9为基准，比9小的分在左边子数列中，比9大的分在右边子数列中经过一轮分组后，只会分成一组【8，7】，再次递归处理【8，7】，至此排序完毕。

快速排序的程序quicksort.py的代码如下：

def quicksort(ilist):
less = [] # 小于基准元素的放到这个列表中
equal = [] # 等于基准元素的放到这个列表中
greater = [] # 大于基准元素的放到这个列表中
if len(ilist) > 1:
pivot = ilist[len(ilist)-1] # 取数组最后一个元素作为基准元素
for x in ilist:
if x < pivot: # 小于基准元素的放到列表less中
less.append(x)
elif x == pivot: # 等于基准元素的放到这个列表中
equal.append(x)
elif x > pivot: # 大于基准元素的放到列表greater中
greater.append(x)
return quicksort(less)+equal+quicksort(greater) # 将三部分拼接起来
else: # 只有一个元素的时候直接返回
return ilist

测试快速排序方法，代码如下：