快速排序
取一个元素p（第一个元素）,使元素p归位
列表被p分成两部分，左边都比p小，右边都比p大
递归完成排序
算法关键点
- 整理
- 递归（递归深度）
排序方法 |
最好情况 |
一般情况 |
最坏情况 |
快速排序 |
O(nlogn) |
O(nlogn) |
O(n^2) |
冒泡排序 |
O(n) |
O(n^2) |
O(n^2) |
代码实现
import random # 分区函数 def partition(lst, left, right): tmp = lst[left] while left<right: while left<right and lst[right]>=tmp: right -= 1 lst[left] = lst[right] while left<right and lst[left]<=tmp: left += 1 lst[right] = lst[left] lst[left] = tmp return left # 快速排序 def quick_sort(lst, left, right): if left < right: mid = partition(lst, left, right) quick_sort(lst, left, mid-1) quick_sort(lst, mid+1, right) lst = list(range(10)) random.shuffle(lst) quick_sort(lst, 0, len(lst)-1) print(lst) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
