首页人工智能技术资讯正文

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

更新时间:2023-03-24 来源:黑马程序员 浏览量:

快速排序(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

测试快速排序方法,代码如下:

1679636428183_图3.png


分享到:
在线咨询 我要报名
和我们在线交谈!