• Python算法——快速排序


    快速排序(Quick Sort)是一种高效的分治排序算法,它选择一个基准元素,将数组分成两个子数组,小于基准的放在左边,大于基准的放在右边,然后递归地排序子数组。快速排序通常比冒泡排序和选择排序更高效,特别适用于大型数据集。本文将详细介绍快速排序的工作原理和Python实现。

    快速排序的工作原理

    快速排序的基本思想是:

    1. 选择一个基准元素(通常是数组中的某个元素)。
    2. 将数组分成两个子数组,一个包含小于基准的元素,另一个包含大于基准的元素。
    3. 递归地对两个子数组进行排序。

    分治的关键在于如何选择基准元素以及如何分割数组。一种常见的方法是选择数组中间的元素作为基准,然后将数组分成两部分,一部分包含小于基准的元素,另一部分包含大于基准的元素。然后,递归地对这两部分进行排序。

    下面是一个示例,演示快速排序的过程:

    原始数组:[6, 5, 3, 1, 8, 7, 2, 4]

    1. 选择基准元素(通常选择中间元素,如 3)。
    2. 分割数组,小于 3 的元素在左边,大于 3 的元素在右边:[2, 1, 3, 5, 8, 7, 6, 4]
    3. 递归地对左边的子数组进行排序,结果为 [1, 2, 3]。
    4. 递归地对右边的子数组进行排序,结果为 [4, 5, 6, 7, 8]。
    5. 合并两个子数组,得到排序后的数组:[1, 2, 3, 4, 5, 6, 7, 8]。

    Python实现快速排序

    下面是Python中的快速排序实现

    def quick_sort(arr):
        if len(arr) <= 1:
            return arr
    
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
    
        return quick_sort(left) + middle + quick_sort(right)
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • arr 是待排序的数组。
    • 如果数组长度小于等于 1,则已经有序,直接返回。
    • 选择基准元素 pivot,通常选择中间元素。
    • 使用列表推导式将数组分成三部分:小于 pivot、等于 pivot 和大于 pivot 的元素。
    • 递归地对左右两部分进行排序,然后合并结果。

    示例代码

    下面是一个使用Python进行快速排序的示例代码:

    def quick_sort(arr):
        if len(arr) <= 1:
            return arr
    
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
    
        return quick_sort(left) + middle + quick_sort(right)
    
    # 测试排序
    arr = [6, 5, 3, 1, 8, 7, 2, 4]
    sorted_arr = quick_sort(arr)
    print("排序后的数组:", sorted_arr)
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    时间复杂度

    快速排序的平均时间复杂度为 O(n log n),其中 n 是数组的长度。它是一种高效的排序算法,通常优于冒泡排序和选择排序。然而,在最坏情况下,时间复杂度可能达到 O(n^2)。

    总之,快速排序是一种高效的排序算法,通过选择基准元素和分割数组,递归地对子数组进行排序,实现了对数组的快速排序。了解快速排序有助于理解排序算法的高效性,并为大型数据集的排序提供了一个强大的工具。

  • 相关阅读:
    PostgreSQL(二)Procedural Language使用的最佳实践
    Databricks notebook里面插入图片步骤图示
    linux安裝maven
    第4章 文件IO
    图解LeetCode——669. 修剪二叉搜索树(难度:中等)
    如何快速检测是否为空白字符
    不止八股:阿里内部语雀一些有趣的并发编程笔试题2——手写限流器
    装备制造企业是否要转型智能装备后服务型公司?
    2022年 安全智能分析技术白皮书 模型开发
    Leetcode376. 摆动序列
  • 原文地址:https://blog.csdn.net/weixin_46178278/article/details/134195212