快速排序算法

开始学习编程算法，遇到排序问题，一般都是用冒泡法，因为冒泡法好理解，代码量少。但是这种算法时间复杂度高，当需要排序的元素较多时，程序运行时间很长，因此产生了快速排序算法，快排算法也是面试中常考的算法。

实现思路

1) 从待排序序列中任选一个元素（假设为 pivot）作为中间元素，将所有比 pivot 小的元素移动到它的左边，所有比 pivot 大的元素移动到它的右边；

2) pivot 左右两边的子序列看作是两个待排序序列，各自重复执行第一步。直至所有的子序列都不可再分（仅包含1个元素或者不包含任何元素），整个序列就变成了一个有序序列。

简单理解，快速排序就是一个挖坑填数的过程，建议先手推赋值过程，完全理解后再写代码。

参考教程：https://www.bilibili.com/video/BV1pt411G7ik

举例说明

用快速排序算法对 [27, 14, 35, 10, 3, 33] 实现升序排序过程如下：

1) 以27为轴，将数据分为左右两部分；

3, 14, 10, (27), 35, 33

2) 对27左边的部分，以3为轴划分两部分；

(3), 14, 10, (27), 35, 33

3) 对3右边的部分，以14为轴划分两部分：

(3), 10, (14), (27), 35, 33

4) 对27右边的部分，以35为轴划分两部分，排序完成

(3), 10, (14), (27), 33, (35)

代码示例

def quick_sort(arr, start, end):
    if start >= end:
        return 
    l,r = start,end
    pivot = arr[l]
    while l < r:
        while l < r and arr[r] >= pivot:
            r -= 1
        arr[l] = arr[r]
        while l < r and arr[l] <= pivot:
            l += 1
        arr[r] = arr[l]
    arr[l] = pivot

    quick_sort(arr, start, l - 1)
    quick_sort(arr, l + 1, end)

lst = [27, 14, 35, 10, 3, 33]
quick_sort(lst, 0, len(lst) - 1)
print(lst)

时间复杂度

快速排序算法，虽然涉及到递归，但依然可以用近似推演的方式，推算其时间复杂度，其理想状态的时间复杂度为O(nlogn)，最坏情况下的时间复杂度为O(n^2)。