快速排序(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测试快速排序方法，代码如下：
本文来自投稿，不代表重蔚自留地立场，如若转载，请注明出处https://www.cwhello.com/366913.html
如有侵犯您的合法权益请发邮件951076433@qq.com联系删除
