python算法之快速排序（Quick Sort）-Toy模板网

这篇具有很好参考价值的文章主要介绍了python算法之快速排序（Quick Sort）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

时间复杂度	名称	示例算法
O(1)	常数时间复杂度	哈希表查找
O(logn)	对数时间复杂度	二分查找
O(n)	线性时间复杂度	遍历数组
O(nlogn)	线性对数时间复杂度	快速排序
O(n^2)	平方时间复杂度	冒泡排序、插入排序
O(n^3)	立方时间复杂度	矩阵乘法
O(2^n)	指数时间复杂度	穷举搜索
O(n!)	阶乘时间复杂度	旅行商问题

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

一、快速排序

快速排序（Quick Sort）是一种基于分治思想的排序算法，是目前使用最广泛的排序算法之一。其基本思想是选取一个基准元素，然后将数组分成小于等于基准的子数组和大于基准的子数组，再递归地对这两个子数组进行快速排序，最后将它们合并起来即可。

二、快速排序步骤

快速排序： 的核心操作是分割数组操作
划分操作采用两种方式：Lomuto 分割和 Hoare 分割。

Lomuto 分割比较简单，但是在特定情况下会导致快速排序的时间复杂度退化为 O(n^2)
Hoare 分割较为复杂，但是效率更高，通常被认为是优化后的快速排序算法 nlong

复杂度

最坏复杂度 n^2

平均复杂度 nlong

递归复杂度 nlong

复杂度
最坏复杂度	n^2
平均复杂度	nlong
递归复杂度	nlong

快速排序的基本步骤：文章来源地址https://www.toymoban.com/news/detail-762341.html

选取数组中的一个元素作为基准元素（通常是数组的第一个元素）。
将数组中比基准元素小的元素移动到数组的左边，将比基准元素大的元素移动到数组的右边。
对左右两边的数组分别重复上述操作，直到所有数组都有序为止。

选择数组第一位元素位基准值，创建两个新数组，分别存放小于基准值和大于基准值的元素
然后这两个新数组递归进行上述操作(再选新数组，再分组)，直到数组为空
然后将左右数组和基准值进行拼接

三、应用例子

def quicksort(arr):
    # 如果数组长度小于等于1，则直接返回该数组
    if len(arr) <= 1:
        return arr
    else:
        # 选择第一个元素作为基准
        pivot = arr[0]
        # 构造小于等于基准的元素构成的子数组 less  构造大于基准的元素构成的子数组 greater
        less = [x for x in arr[1:] if x <= pivot]      # 输出比第一个元素小的列表
        greater = [x for x in arr[1:] if x > pivot]    # 输出比第一个元素大的列表
        print('less-----------', less)
        print('greater-----------', greater)
        # 递归地对这两个子数组进行快速排序，然后将它们合并起来，并加上基准元素
        return quicksort(less) + [pivot] + quicksort(greater)
        
if __name__ == '__main__':
    arr = [3, 5, 2, 8, 1, 4]
    sorted_arr = quicksort(arr)
    print(sorted_arr)

选择基准元素：从待排序数组中选择一个元素作为基准（通常选择第一个元素）
分割数组： 重新排列数组，将所有小于基准的元素放在基准的左边，所有大于基准的元素放在基准的右边，等于基准的元素可以放在任意一边。此时，基准元素的位置也已经确定
递归排序： 递归地对基准元素左边的子数组和右边的子数组进行快速排序
合并结果： 将左边子数组、基准元素、右边子数组依次拼接起来，得到排好序的数组

到了这里，关于python算法之快速排序（Quick Sort）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！