原理
将列表中第一个元素设定为基准数字,赋值给mid变量,然后将整个列表中比基准小的数值放在基准的左侧,比基准大的数字放在基准右侧。然后将基准数字左右两侧的序列在根据此方法进行排放。
定义两个指针,low指向最左侧,high指向最右侧
然后对最右侧指针进行向左移动,移动法则是,如果指针指向的数值比基准小,则将指针指向的数字移动到基准数字原始的位置,否则继续移动指针。
如果最右侧指针指向的数值移动到基准位置时,开始移动最左侧指针,将其向右移动,如果该指针指向的数值大于基准则将该数值移动到最右侧指针指向的位置,然后停止移动。
如果左右侧指针重复则,将基准放入左右指针重复的位置,则基准左侧为比其小的数值,右侧为比其大的数值。
代码实现:
def sort(alist,start, end):
low = start
high = end
if low > high:
return
mid = alist[low] # 基数
while low < high:
# high偏移(右侧部分)
while low < high:
if alist[high] > mid: # 比基准值大,不需要移动,将high左移
high -= 1
else: # 比基准值小时,将它移动到基准值所在位置
alist[low] = alist[high]
break #中断右侧的high的偏移,转而从左侧偏移
# low 偏移 (左侧部分)
while low < high:
if alist[low] < mid:# 比基准值小,向右偏移
low += 1
else:# 比基准值大,将high批向当前位置
alist[high] = alist[low]
break
if low == high:
alist[low] = mid
sort(alist, start, high-1) # 处理基数左部分
sort(alist, low + 1, end) # 处理基数右部分
return alist
将上面的代码分解成两个函数的形式,一部分执行元素的移动,一部分执行递归,这种形式是比较常见的形式
def partition(alist,start, end):
low = start
high = end
mid = alist[low] # 选择基准值
while low < high:
# 从右侧向左处理
while low < high:
if alist[high] > mid:
high -= 1 # high左移
else: # 如果比基准值小,互换
alist[low] = alist[high] # 将右侧的值移动到基准值所在位置(这里是最左侧)
break # 结果当前循环
# 从左向右处理
while low < high:
if alist[low] < mid:
low += 1 # low 右移
else:# 比基值大,将high移动到此位置
alist[high] = alist[low]
break
if low == high:# 当两个指针重叠时,以此为基值,右侧是比基值小,右侧比基值大
alist[low] = mid
return low # 此时high = low, 返回任意一个都行.分别作变左侧的high,右侧部分的low,并重复上面的步骤
def quick_sort(alist, start, end):
if end > start:
index = partition(alist, start, end) # 此处index下标
quick_sort(alist, start, index-1) # 处理左侧部分
quick_sort(alist,index+1, end ) # 处理右侧部分