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

实现思路

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)。

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/211