【算法图解】 之 [快速排序] 详解

2019/7/22 18:13:15 人评论 次浏览 分类:学习教程

知识共享许可协议 版权声明:署名,允许他人基于本文进行创作,且必须基于与原先许可协议相同的许可协议分发本文 (Creative Commons)

入门算法学习,看的第一本是深入浅出的《算法图解》一书,本博客是对《算法图解》一书的学习笔记,将书中的分享的算法示例用Python3语言实现。
如果你也想要阅读这本书,百度云盘链接:https://pan.baidu.com/s/1s967vfgEBd1vSrfwVI9Y3g 提取码:【be9k】
或者也可以留言你的邮箱,我将PDF共享给你~

快速排序

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

快速排序工作原理

对排序算法来说,最简单的数组什么样呢?还记得前一节的“提示”吗?就是根本不需要排序的数组。
在这里插入图片描述
因此,基线条件为数组为空或只包含一个元素。在这种情况下,只需原样返回数组——根本就不用排序。

我们来看看更长的数组。对包含两个元素的数组进行排序也很容易。
在这里插入图片描述
包含三个元素的数组呢?
在这里插入图片描述
别忘了,你要使用D&C,因此需要将数组分解,直到满足基线条件。

下面介绍快速排序的工作原理。

  • 首先,从数组中选择一个元素,这个元素被称为基准值(pivot)。
  • 稍后再介绍如何选择合适的基准值。我们暂时将数组的第一个元素用作基准值。
  • 接下来,找出比基准值小的元素以及比基准值大的元素。
    在这里插入图片描述
    这被称为分区(partitioning)。现在你有:
    • 一个由所有小于基准值的数字组成的子数组;[15, 10]
    • 基准值[33]
    • 一个由所有大于基准值的数组组成的子数组。[ ]

因此只要对这两个子数组进行快速排序,再合并结果,就能得到一个有序数组!
quicksort([15, 10]) + [33] + quicksort([ ])
--->[10, 15,33] 一个有序数组

包含四个元素的数组呢?
在这里插入图片描述
左边的子数组包含三个元素,而你知道如何对包含三个元素的数组进行排序:对其递归地调用快速排序。
在这里插入图片描述
包含五个元素的数组呢?
在这里插入图片描述
例如,假设你将3用作基准值,可对得到的子数组进行快速排序。
在这里插入图片描述
将子数组排序后,将它们合并,得到一个有序数组。即便你将5用作基准值,这也可行。
在这里插入图片描述
将任何元素用作基准值都可行,因此你能够对包含五个元素的数组进行排序。同理,你能够
对包含六个元素的数组进行排序,以此类推。。。

快速排序–案例

案例:实现上述快速排序的代码

def quicksort(arr):
    if len(arr) < 2:         # 基线条件 数组为空或只有一个元素的数组返回数组本身
        return arr

    pivot = arr[0]           # 递归条件 基准值

    less = [i for i in arr[1:] if i <= pivot]    # 小于基准值的元素构成的数组

    greater = [i for i in arr[1:] if i > pivot]  # 大于基准值的元素构成的数组

    return quicksort(less) + [pivot] + quicksort(greater)  # 合并基线两侧的数组


s = quicksort([4, 1, 4, 7, 6, 7, 2, 3, 5])
print(s)

------------------------------------------
[1, 2, 3, 4, 4, 5, 6, 7, 7]

运行时间-----大 O 表示法

快速排序的独特之处在于,其速度取决于选择的基准值。

在讨论快速排序的运行时间前,我们再来看看最常见的大O运行时间。
在这里插入图片描述
上述图表中的时间是基于每秒执行10次操作计算得到的。这些数据并不准确,这里提供它们只是想让你对这些运行时间的差别有大致认识。实际上,计算机每秒执行的操作远不止10次。

在平均情况下,快速排序的运行时间为O(n log n)。

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->