1. 快速排序思想
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列的目的。
2. 快速排序实现步骤
假设有一个列表[5,7,3,3,6,2,1,4,10]，需要使用快速排序，将其排序为有序列表。
2.1 第一次排序
- 首先，将列表的首个元素作为中间值，使用mid_value接收。【mid_value =5】
- 创建两个游标，low游标放置于0号索引位置【开头】，high游标放置于n-1索引位置【末尾】
step1
- 先移动high游标，当high游标所指元素比mid_value大时，high游标左移【移到4】
- 当high游标所指元素比mid_value小时，游标停留在当前位置【移动到4时，4比mid_value小，则high游标停留在当前位置】
- 将high游标当前位置的元素的值赋给low游标所指的位置【5 --> 4】
step2
- low游标往右走，当low游标所指的元素比mid_value小时，low游标右移【移到7】
- 当low游标所指的元素比mid_value大时，游标停留在当前位置【移动到7时，7比mid_value大，则low游标停留在当前位置
- 将low游标当前位置的元素赋值给high游标所指的位置【4 --> 7】
step3
- high游标当前位置的元素变为7后，当前值比mid_value大，所以high游标可以继续往左走，1的值比mid_value小，则high游标停留在当前位置
-
将high游标当前位置的元素赋值给low游标所指的位置，即7 --> 1
step4
- low游标当前位置的元素变为1后，当前值比mid_value小，所以low游标可以继续往右走。不断和右边的元素比较，如果比mid_value小，则继续右移，直到去到6元素所在的位置，6比mid_value大，所以low游标停留在当前位置
- 将low游标所处位置的元素的值赋值给high游标所指位置，即1 --> 6
step5
- high游标继续往左走，2比mid_value小，所以high停留在当前位置
- 将high游标所指位置元素的值赋值给low游标所指位置，即6 --> 2
step6
- low游标往右走，此时low和high游标重合
- 当low和high相等时，将mid_value赋值给此时位置的元素
step7
以上便是第一次排序的过程图
通过以上过程，可以实现以下代码
def quick_sort(target_list):
n = len(target_list)
# 将alist的第一个元素作为中间值
mid_value = target_list[0]
low = 0
high = n-1
# 当low小于high时，两个游标都可以移动
while low < high:
# high游标所对应元素比mid_value大时，high游标往左走
while low < high and target_list[high] > mid_value:
high -= 1
# 当条件不满足时说明遇到的元素比mid_value小
# 此时将high游标所处位置的元素放到low游标所处的位置
target_list[low] = target_list[high]
while low < high and target_list[low] < mid_value:
# low游标往右走
low += 1
target_list[high] = target_list[low]
# 从循环退出时，low游标和high游标位置重合,把mid_value放到此位置
target_list[low] = mid_value
2.2 第n次排序
根据快速排序的思想，我们排序好中间值后，会对中间值左边的列表和右边的列表再次使用快速排序，核心部分的代码基本不变，因此我们可以使用递归的方法来完成多次排序。
8.png
- 由于我们需要在同一个list上操作，因此不能使用列表切片的方式传入进行递归，我们需要传入first和last参数，用于表示截取同一个列表。first代表起使位置索引，last代表末尾位置索引
- 递归时，左边的列表就可以表示为quick_sort(alist,first,low-1);右边的列表可以表示为quick_sort(alist,low+1,last)
- 当列表只有一个元素或没有元素的时候，就终止递归，即first >= last时，结束递归
- 代码实现
def quick_sort(target_list,first,last):
# 当first大于等于last时，则终止递归
if first >= last:
return
# 将alist的第一个元素作为中间值
mid_value = target_list[first]
# 设置low和high两个游标
low = first
high = last
while low < high:
# high 左移,可以把相等的情况放到high或者low任意一边处理
while low < high and target_list[high] >= mid_value:
high -= 1
target_list[low] = target_list[high]
# low右移
while low < high and target_list[low] < mid_value:
low += 1
target_list[high] = target_list[low]
# 从循环退出时，low = high
target_list[low] = mid_value
# 把mid_value左右分为两部分进行递归操作
# 对mid_value左边的元素进行递归操作
quick_sort(target_list,first,low-1)
# 对mid_value右边的元素进行递归操作
quick_sort(target_list,low+1,last)
return target_list
网友评论