《算法图解》NOTE 4 快速排序法1.递归与分治法2.快速排序法的实现3.快速排序法的时间复杂度(用渐近表示法表示)

这是《算法图解》的第四篇读书笔记,主要涉及快速排序法。

1.递归与分治法

快速排序法(quick sort)之所以有这个名称,源于其排序速度,相较于其他排序方式来说,较快。而其高排序效率,主要源于其使用了分治法(divide and conquer)的思路。 所谓分治法,即分而治之,将一个问题划分为几个子问题,而后解决子问题。当然,子问题可以再分解为几个子问题,直到子问题不能再划分时,解决不能再划分的子问题。若有需要,可以将子问题的答案合并,作为原问题的答案。请注意,解决问题的方法一直保持不变。 为什么上述的思路可行呢,简单来说,可用数学归纳法进行说明。 对与规模为n的原问题,需证明解决方案: 在问题规模为n时可行的时候: n=1(最小规模的问题)可行, 同时规模为n+1时仍可行。 具体的数学证明,请参考相关的资料。 分治法的思路是否和上一篇读书笔记所述的递归(recursion)相似呢。实,分治法是通过递归实现的。

2.快速排序法的实现

如上文所说,快速排序法应用了分治法的思想。其具体思路如下: 1.从原序列中选择一个数作为基础值 2.将原序列中的元素按照与基础值的大小比较结果,分为大于基础值、小于基础值两个序列:S1和S2. 3.将元素列按照S1、基础值和S2的顺序组合成一个新序列并将新序列返回。 4.分别将S1和S2重复步骤1、步骤2和步骤3。 5.重复步骤4,直到划分后的序列只有一个或零个元素,此时直接返回含有单个元素或0个元素的序列。 代码如下:

#演示快速排序法,排序结果以降序显示
def quick_sort(seq):
    #基线条件
    if len(seq)<2:
        return seq
    base_value=seq[0]
    less=[]
    large=[]
    #划分子序列
    for idx in range(1,len(seq)):
        if base_value>=seq[idx]:
            less.append(seq[idx])
        else:
            large.append(seq[idx])
    return quick_sort(large)+[base_value]+quick_sort(less)

seq=[10,15,12,18,15,1]
print(quick_sort(seq))

3.快速排序法的时间复杂度(用渐近表示法表示)

基于分治思想的快速排序法,其时间复杂度为n*log2 n 。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Lambda

JavaScript排序算法详解

JS家的排序算法 引子 有句话怎么说来着: 雷锋推倒雷峰塔,Java implements JavaScript. 当年,想凭借抱Java大腿火一把...

2718
来自专栏申龙斌的程序人生

零基础学编程028:面向对象编程OOP

在《零基础学编程021:获取股票实时行情数据》一节中,我们想获取6支股票的行情数据,在《零基础学编程022:函数的世界》里我们能够把重复性的代码封装为一个函数p...

2986
来自专栏Java帮帮-微信公众号-技术文章全总结

Java面试系列5

一、是否可以继承String类? String类是final类故不可以继承。 二、面向对象的特征有哪些方面 1.抽象: 抽象就是忽略一个主题中与当前目标无关的...

3545
来自专栏我和我大前端的故事

数据结构学习☞入门(一)算法数据结构

编程如果只是一个为了解决生活温饱的工具,那你可以完全忽略数据结构,算法,你的目标很容易实现;但如果你是热爱编程,把它当做对生活的追求,想在这一行走的更远,更久,...

873
来自专栏Python私房菜

翻译 | 更快的Python(二)

更快的Python使用代码示例来说明如何书写Python代码能带来更高的性能。本文对代码进行了讲解,从性能和可读性等角度来选择出最适合的写法。

843
来自专栏绿巨人专栏

Category Theory: 01 One Structured Family of Structures

\(G = \{ G, +, e \}\),一个数据集\(G\),一个二元操作符\(+\),和一个幺元\(e\)。

1043
来自专栏我是攻城师

理解递归算法的原理

递归(Recursion)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法,其核心思想是分治策略。 递归式方法可以被用于解决很多的计算机科...

8741
来自专栏C语言及其他语言

[每日一题]矩阵问题

今天给大家分享的是二维数组的基本用法,主要是利用数组对行列的控制 题目描述 求一个3×3矩阵对角线元素之和。 输入 矩阵 输出 主对角线 副对角线 元素和 ...

3167
来自专栏HTML5学堂

算法之旅 | 冒泡排序法

HTML5学堂-码匠:本期继续走入算法 —— 冒泡排序法。冒泡排序算法相对简单,容易上手,稳定性也比较高, 算是一种较好理解的算法,也是面试官高频提问的算法之一...

3939
来自专栏计算机视觉与深度学习基础

Leetcode 15 3Sum + 有趣的小BUG

Given an array S of n integers, are there elements a, b, c in S such that a + b...

2156

扫码关注云+社区