python实现快速排序

---

快速排序

基本原理

选择待排序列第一个元素作为参照点，将列表分为左右两个列表，左列表元素均比参照点小，右列表元素均比参照点大，然后递归左右两个列表。

代码

# -*- coding: utf-8 -*-
'''
基本思想：
    选择待排序列中一个数字，将列表分为左右两个列表，左边比数小，右边比数大。
    然后递归调用。
'''
def quick_sort(input_list):

    if len(input_list) <= 1:    # 长度为1则直接返回
        return input_list
    left = []
    right = []
    for ele in input_list[1:]:  # 循环里面的元素
        if ele>=input_list[0]:  # 若当前元素>第一个数字
            right.append(ele)
        else:                   # 若当前元素<第一个数字
            left.append(ele)
    return quick_sort(left) + [input_list[0]] + quick_sort(right)
if __name__ == '__main__':
    pre_list = [1,6,3,3,7]
    res = quick_sort(pre_list)
    print(res)

图解

由于涉及到递归，可能直观上不好理解。于是在次贴出一张手写图。字烂。

不过强烈建议读者静下心来自己绘制一遍。

易忘点和易错点

a. 不要忘记列表 长度为1 的情况。
b. 在return语句中，由于使用 + 号合并多个list，因此需要将参照点也转成一个 list 。即 [input_list[0]] 。

---

原文链接：https://blog.csdn.net/wulele2/article/details/111174932

---