快速排序
- [ ] 快速排序：快
- [ ] 快排思路：
- 取一个元素p(第一个元素)，使元素p归位
- 列表被p分成两部分，左边都比p小，右边都比p大；
- 递归完成排序。
例如：
选择5作为基准数。从右向左扫描，寻找比基准数小的数字为1，交换5和1的位置，[1,3,4,6,2,9,8,5,7]，接着从左向右扫描，寻找比基准数大的数字为6，交换5和6的位置，[1,3,4,5,2,9,8,6,7]。重复上述过程，直到基准数左边的数字都比其小，右边的数字都比其大。然后分别对基准数左边和右边的序列递归进行上述方法。
排序前：[5,3,4,6,2,9,8,1,7]
p归位：[3,4,2,1,5,6,9,8,7]
目标：[1,2,3,4,5,6,7,8,9]
关键点
1. 归位
2. 递归
代码实现：
import sys
import random
from timewrap import exe_time
sys.setrecursionlimit(10000) # 设置递归深度
def partition(data,left,right):
tmp = data[left]
while left < right:
while left < right and data[right] >= tmp:
right -= 1
data[left] = data[right]
while left < right and data[left] <= tmp:
left += 1 # 你比我小，那么你就往我前面放，我往后走一个
data[right] = data[left]
print('data[left]===',data[left])
print('data[right]===',data[right])
data[left] = tmp # 最后的时候，它左边是比他小的，右边是比它大的。
return left
# 归位完成
# 归位完成后，左边和左边比，右边和右边比。
# 所以才会有下面quick_sort(data,left,mid-1)意指从0开始到定位完-1的位置比，也就是左边比
# quick_sor(data,mid+1,right)则就是大的排序
# 递归排序
def _quick_sort(data,left,right):
if left < right:
mid = partition(data,left,right)
_quick_sort(data,left,mid-1)
_quick_sort(data,mid+1,right)
@exe_time
def quick_sort(li):
return _quick_sort(li,0,len(li)-1)
@exe_time
def sys_sort(li):
li.sort()
li = list(range(10000))
random.shuffle(li)
quick_sort(li) # quick_sort running time：-0.06963086128234863 secs.
# sys_sort(li) # sys_sort running time：-0.003387928009033203 secs.
