【经典排序】快速排序

1.快速排序

选取第一个数为基准值，把比基准值大的放在左边，小的放在右边，依次遍历，最后有序
快速排序总是优于归并排序

2.代码实现

def quick_sort(my_list, start, end):
    if start >= end:
        return
    mid = my_list[start]
    low = start
    height = end
    while low < height:
        while low < height and mid <= my_list[height]:
            height -= 1
        my_list[low] = my_list[height]
        while low < height and mid > my_list[low]:
            low += 1
        my_list[height] = my_list[low]
    my_list[low] = mid

    quick_sort(my_list, start, low - 1)
    quick_sort(my_list, low + 1, end)
    
if __name__ == '__main__':
    pass
    a = [5, 6, 1, 9, 0, 4, 6, 8]
    print(a)
    quick_sort(a, 0, len(a) - 1)
    print(a)

3.复杂度

最优时间复杂度： O(nlogn)
最坏时间复杂度： O(n^2)
平均时间复杂度： O(nlogn)
稳定性：不稳定