Python里实现快速排序的方法

快速排序由C. A. R. Hoare在1962年提出，它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

具体实现步骤如下：

1、先从数列中取出一个数作为基准数

2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边

3、再对左右区间重复第二步，直到各区间只有一个数

Python里代码实现：

# Autor: 5bug
# WebSite: http://www.5bug.wang

#快速排序
def partition(data, left, right):
    pivot = data[left]
    while left < right:
        while left < right and data[right] >= pivot:
            right -= 1
        data[left] = data[right]
        while left < right and data[left] <= pivot:
            left += 1
        data[right] = data[left]
    data[left] = pivot
    return left

def quick_sort(data, left, right):
    if left < right:
        mid = partition(data, left, right)
        quick_sort(data, left, mid - 1)
        quick_sort(data, mid + 1, right)
    return data


if __name__ == "__main__":
    data = [1, 6, 2, 3, 9, 1, 5, 4, 0]
    print(quick_sort(data, 0, len(data) - 1))

注：快速排序算法是一个不稳定排序算法，但是是一个排序效率极高的算法，时间复杂度也为O(nlogn)。

如果想深入了解具体的排序过程，可参考如下文章：https://www.cnblogs.com/chengxiao/p/6262208.html