Python里实现快速排序的方法

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

具体实现步骤如下:

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

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

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

网上搜了个示意图如下:Sorting_quicksort_anim.gif

Python里代码实现:

# Autor: 5bug
# WebSite: http://www.XuePython.wang
# 学Python网QQ群: 643829693

#快速排序
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


分享:

扫一扫在手机阅读、分享本文