1. 思路
- 从序列中任选一个元素（temp）作为中间数，
- 列表分为两部分，把所有比 temp小的数移动到它的左边，再所有比 temp大的数移动到它的右边（简单理解：左边都比temp小，右边都比temp大）
- 分别对左右两部分进行递归，直到左右两部分剩余一个元素
2. 举例
比如现在有列表： a = [6,7,4,1,8,5,3,9,2]
- 先从列表中找 6 作为中间数，将列表分为两部分（6的左边比6小，右边比6大）
- 对于左半部分，重复第一步的操作
- 右半部分也是一样
3. 详细步骤分析
列表： a = [6,7,4,1,8,5,3,9,2]
- 先从列表中找 6 作为中间数，将列表分为两部分（6的左边比6小，右边比6大）
2. 左半部分
1. 在 [2, 3, 4, 1, 5, 6, 8, 9, 7] 基础上进行的
2. 左半部分为 2,3,4,1,5
3. 选择第一个元素 2 作为temp，将剩余元素分为 [1,2] 和 [4,3,5] 两个部分
1,2,4,3,5 的右半部分
[4,3,5]
3. 右半部分
4. 代码实现
# ① 列表分为两部分，大的在temp右 小的在temp左
def fun(data,left,right):
temp = data[left]
print('temp:',temp)
while left < right:
while left < right and data[right]>=temp: # 1. 从右边开始找比temp小的数
right -=1 # 如果比temp大 就向左边走一步
data[left] = data[right] # 把右边的值写到左边空位上
print(data,'right right下标:',right)
while left<right and data[left]<=temp: # 2. 从左边开始找比temp大的数
left+=1 # 如果比temp小 就向右边走一步
data[right] = data[left] # 把左边的值写到右边空位上
print(data,'left left 下标:',left)
data[left] = temp # temp归位
print('temp归位:{} temp下标{}:'.format(data,left))
return left
# ② 分别对左右两部分进行递归
def quick_sort(data,left,right):
if left<right:# 至少有两个元素
mid=fun(data,left,right)
print('----------------------')
quick_sort(data,left,mid-1)
quick_sort(data,mid+1,right)
# ③ 调用
a = [6,7,4,1,8,5,3,9,2]
print('排序前：',a)
# a = [6,1,2,7,9,3,4,5,10,8]
# a = [5,7,4,6,3,1,2,9,8]
quick_sort(a,0,len(a)-1)
print('排序后：',a)
def quick_sort(data):
if len(data) < 2:
return data
else:
temp = data[0]
less = [i for i in data[1:] if i <= data[0]]
greater = [i for i in data[1:] if i > data[0]]
print(less + [temp] + greater)
return quick_sort(less) + [temp] + quick_sort(greater)
a = [6,7,4,1,8,5,3,9,2]
print(quick_sort(a))
