快速排序
取一个元素p（第一个元素）,使元素p归位
列表被p分成两部分，左边都比p小，右边都比p大
递归完成排序

算法关键点

• 整理
• 递归（递归深度）

代码实现

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]
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
 

文章来源: pengshiyu.blog.csdn.net，作者：彭世瑜，版权归原作者所有，如需转载，请联系作者。

原文链接：pengshiyu.blog.csdn.net/article/details/80672595