快速排序
快速排序是冒泡排序的一种改进，比基准值小的放到前面，比基准值大的放到后面，不断递归，直到数组只有一个数据，然后返回数组
在数组顺序为倒序的时候使用快排，会使快排退化成冒泡算法
第一种
这种比较常见，也是速度最快的
def partition(arr, left, right):
# 以最左边的值为基准
key = arr[left]
while left < right: # 左游标小于右游标
while left < right and arr[right] >= key: # 从右边开始遍历，比基准值大或等于基准值 游标减1
right -= 1
arr[left] = arr[right] # 如果比基准值小 跳出循环 赋值到左边
while left < right and arr[left] <= key:# 从左边开始遍历，比基准值小或等于基准值 游标加1
left += 1
arr[right] = arr[left] # 如果比基准值小 跳出循环 赋值到左边
arr[left] = key # 当左右游标相等时，遍历完毕，把基准值赋值到左右游标相等的位置
return left
def quickSort(arr, left, right):
if left >= right: # 左游标大于等于右游标 递归结束
return arr
high = right # 左右游标传递到 partition的时候会被改变
low = left # 所以设置两个变量值保存 以便后面使用
p = partition(arr, left, right) # 基于基准值两边筛选数据
quickSort(arr, low, p-1) # 递归比基准值小的区间
quickSort(arr, p+1, high) # 递归比基准值大的区间
test = [4,3,6,2,7,1,8]
quickSort(test, 0, 6)
print(test)
# 输出
[1, 2, 3, 4, 6, 7, 8]
第二种
这种是在《图解算法》的书上看到的，刚看上去的时候，个人感觉就比不上第一种
def quickSort(arr):
if len(arr) <= 1: # 列表长度小于等于1的时候 结束递归
return arr
key = arr[0] # 基准值为列表第一个值
left = [i for i in arr[1:] if i < key] # 全部遍历一遍，小于基准值的放到left
right = [j for j in arr[1:] if j >= key] # 全部遍历一遍，等于或者大于基准值放到right
return quickSort(left) + [key] + quickSort(right)
因为每次遍历都要遍历整个列表，循环次数相当于第一种的两倍，所以，从代码分析来看，确实是要比第一种要慢的，而且空间开销也是要比第一种要大，每次递归就要创建两个列表。
不过这种方式，也是符合快速排序的思想，以一个基准值，不断切分数组
时间对比
在jupyter notebook上简单分析了一下
import random
for i in range(5):
a = random.sample(range(1000000), 500000)
%time a = quickSort1(a, 0, 499999)
print('*'*40)
for i in range(5):
b = random.sample(range(1000000), 500000)
%time quickSort2(b)
#输出
Wall time: 2.11 s
Wall time: 1.92 s
Wall time: 2.04 s
Wall time: 2.1 s
Wall time: 2.07 s
****************************************
Wall time: 2.31 s
Wall time: 2.24 s
Wall time: 2.45 s
Wall time: 2.18 s
Wall time: 2.11 s
50万的测试数据，循环5遍
从时间上可以看出，第二种是要比第一种要慢的
第一种平均时间接近2s
第二种平均时间接2.3s
