python3 快速排序

思路

第一步：找到一个随机的数，一般都是第一个数，也就是left,递归中也用left，放到缓存中，专业叫 基准值，基准值是要放在中间的。

第二步：最左边空出一个位置就是索引left的位置，所以从右向左找比基准值小的索引 R ，找到并将值放在left位置，这样索引R 就会空出来。

第三步：从左向右找比基准值大的索引 L 并将值放在right的位置上。

第四步：循环到left = right，就是基准值的索引，将基准值赋值进去，并返回 基准值索引。

 

第五步：递归排序基准值左边的列表，

第六步：递归排序基准值右边的列表。

def quit_sort(data, left, right):if left < right:mid = partition(data, left, right)quit_sort(data, left, mid - 1) # 最左面到中间quit_sort(data, mid + 1, right) # 中间到最后def partition(data, left, right):tmp = data[left]while left < right:# 从右找到比中间小的值的索引while left < right and data[right] > tmp:right -= 1data[left] = data[right]# 从左找到比中间大的索引while left < right and data[left] < tmp:left += 1data[right] = data[left]data[left] = tmpreturn leftli = list(range(1000)) random.shuffle(li) print(li) quit_sort(li,0,len(li)-1) print(li)

注：python中有最大的递归层数，如果超过会报错，我们需要设置一下

import sys sys.setrecursionlimit(10000)

快排的时间复杂度

最好情况 O(nlongn)

一般情况 O(nlongn)

最差情况 O(n²)

 

转载于:https://www.cnblogs.com/bingabcd/p/7425008.html

总结

以上是生活随笔为你收集整理的python3 快速排序的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。