《算法图解》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大腿火一把...

3078
来自专栏我是业余自学C/C++的

基数排序

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

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

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

1053
来自专栏iKcamp

翻译连载 | 第 9 章:递归(上)-《JavaScript轻量级函数式编程》 |《你不知道的JS》姊妹篇

原文地址:Functional-Light-JS 原文作者:Kyle Simpson-《You-Dont-Know-JS》作者 第 9 章:递归(上) 在下一页...

2269
来自专栏算法channel

其他|二维指针,数组指针,指针数组

望时间的流逝不仅仅丰富了我们的阅历,更重要的是通过提炼让我们得以升华,走向卓越。 1c++ c/c++的重要性毋庸置疑,凡是对性能要求很高的系统和算法,其中核...

3265
来自专栏我是攻城师

理解递归算法的原理

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

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

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

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

3126
来自专栏一个爱吃西瓜的程序员

每天学习一点儿算法--快速排序

快速排序是一种常用的优雅的排序算法,它使用分而治之的策略。 那么分而治之(D&C)是一种怎样的策略呢? 分而治之 分而治之(D&C)的要点只有两个: 找出简单...

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

[每日一题]矩阵问题

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

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

Leetcode 15 3Sum + 有趣的小BUG

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

2316

扫码关注云+社区

领取腾讯云代金券