快排的概念
快排是交换排序的一种，通过一趟排序，将待排数组分割成独立的左右两部分，左边元素均比右边元素小，再通过递归的方式，分别在左右两边继续执行快排，直到有序为止
快排的步骤
- 从待排序的数组中，选取第一个作为基准元素
- 排序数组，将所有比“基准”大的元素放在基准的右边，将所有比“基准”小的元素放在基准的左边
- 分别递归“基准”左侧和右侧的数列
代码实现
def quick_sort(sort_list, start, end):
if start >= end: # 递归退出条件
return
mid = sort_list[start] # 设置起始元素为基准元素
left = start # 从左向右移动的游标
right = end # 从右向左移动的游标
while left < right:
while left < right and sort_list[right] > mid: #左右游标未重合，且右边游标指向的元素大于基准元素，游标向左移动
right -= 1
sort_list[left] = sort_list[right] # 此时，右侧游标指向的元素小于基准元素，替换
while left < right and sort_list[left] <= mid: #左右游标未重合，且左边游标指向的元素小于等于基准元素，游标向右移动
left += 1
sort_list[right] = sort_list[left] # 此时，左侧游标指向的元素大于等于基准元素，替换
sort_list[left] = mid
quick_sort(sort_list, start, left - 1) # 左半边元素递归调用
quick_sort(sort_list, left + 1, end) # 右半边元素递归调用
return sort_list
时间复杂度
最优情况下时间复杂度
每一次取到的元素都刚好平分整个数组，快速排序最优的情况下时间复杂度为：O( nlogn )**
最差情况下时间复杂度
最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)，快速排序最差的情况下时间复杂度为：O( n^2 )**
平均时间复杂度
快速排序的平均时间复杂度也是：O(nlogn)
空间复杂度
首先就地快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据；
最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况
最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况
