快排的概念

快排是交换排序的一种，通过一趟排序，将待排数组分割成独立的左右两部分，左边元素均比右边元素小，再通过递归的方式，分别在左右两边继续执行快排，直到有序为止

快排的步骤

• 从待排序的数组中，选取第一个作为基准元素
• 排序数组，将所有比“基准”大的元素放在基准的右边，将所有比“基准”小的元素放在基准的左边
• 分别递归“基准”左侧和右侧的数列

代码实现

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 ) ；退化为冒泡排序的情况