简介

快速排序是对冒泡排序（Python 实现经典算法之冒泡排序）的一种改进。

顾名思义快速排序就是快，而且效率高！

它是处理大数据最快的排序算法之一了，平均时间复杂度为O(NlogN)。

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

步骤

1. 从数列中挑出一个元素，称为 “基准值”;
2. 重新排序数列，所有元素比基准值小的放在基准值的左边，比基准值大的放在基准值的右边（相同的数可以到任一边）。在这个分区退出之后，该基准值就处于数列的中间位置。这个称为分区（partition）操作，也可以称为一次归位操作，归位操作的过程见下动图；
3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列按照步骤1、2 排序。

动画演示

实例代码

####
# 今日头条：技术好奇心
####

# 分区（归位）操作
def partition(arr, left, right):
    # 归位操作，left，right 分别为数组左边和右边的位置索引
    # 这里tmp默认为此次操作的数组首位
    tmp = arr[left]
    # 只要左右两个指针没有走到一起，就继续进行循环操作
    while left < right:
        # 从右边找比 tmp 小的数，如果比 tmp 大，则移动指针不作操作
        while left < right and arr[right] >= tmp:
            # 将指针左移一个位置
            right -= 1
        # 将右边的值写到左边的空位上
        # （因为前面已经tmp=arr[left]了，所以不用担心arr[left]被覆盖丢失）
        arr[left] = arr[right]
        # 从左边找比 tmp 大的数，如果比 tmp 小，则移动指针，不作任何操作
        while left < right and arr[left] <= tmp:
            # 将指针右移一个位置
            left += 1
        # 将左边的值写到右边的空位上
        arr[right] = arr[left]
    # 循环结束，把 tmp 归位
    arr[left] = tmp
    # 返回 left，right 都可以，目的是便于后面的递归操作对左右两部分进行排序
    return left


# 快速排序
def quick_sort(arr, left, right):
    # 检查数组长度，是否需要进行排序
    if len(arr) <= 1:
        return arr
    # 检查传入参数是否符合规定
    if left < right:
        # 进行分区操作，取中间值(方便后面进行左右区分)
        mid = partition(arr, left, right)
        # 每次分区后打印一次
        print(arr)
        # 对左半部分进行归位操作
        quick_sort(arr, left, mid-1)
        # 对右半部分进行归位操作
        quick_sort(arr, mid+1, right)


if __name__ == "__main__":
    print('今日头条：技术好奇心')
    print('----------- 排序前数组内容 -----------------')
    arr = [5, 7, 4, 6, 3, 1, 2, 9, 8]
    print(arr)
    print('-------------- 开始排序 -----------------')
    quick_sort(arr, 0, len(arr)-1)
    print('------------ 排序后的结果 ------------------')
    print(arr)

运行结果

今日头条：技术好奇心
----------- 排序前数组内容 -----------------
[5, 7, 4, 6, 3, 1, 2, 9, 8]
-------------- 开始排序 -----------------
[2, 1, 4, 3, 5, 6, 7, 9, 8]
[1, 2, 4, 3, 5, 6, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
------------ 排序后的结果 ------------------
[1, 2, 3, 4, 5, 6, 7, 8, 9]

相关文章

Python 实现经典算法之选择排序

Python 实现经典算法之插入排序

Python 实现经典算法之冒泡排序

Python 实现经典算法之归并排序

Python 实现经典算法之希尔排序

Python 实现经典算法之堆排序