《算法图解》第四章笔记与课后练习_快速排序算法

软件环境:Python 3.7.0b4

一、分而治之

工作原理:

  • 找出简单的基线条件;
  • 确定如何缩小问题的规模,使其符合基线条件。
# 4.2
def count(list):
    if list == []:
        return 0
    return 1 + count(list[1:])

# 4.3
def max(list):
    if len(list) == 2:
        return list[0] if list[0] > list[1] else list[1]
    sub_max = max(list[1:])
    return list[0] if list[0] > sub_max else sub_max

4.4:二分查找的基线条件是数组只包含一个元素。如果要查找的值与这个元素相同,就找到了!否则说明它不在数组中。递归条件为 把数组分成两半,将其中一半丢弃,并对另一半执行二分查找。

二、快速排序

def quicksort(array):
  if len(array) < 2:
    # 基线条件:为空或只包含一个元素的数组是“有序”的
    return array
  else:
    # 递归条件
    pivot = array[0]
    # 由所有小于等于基准值的元素组成的子数组
    less = [i for i in array[1:] if i <= pivot]
    # 由所有大于基准值的元素组成的子数组
    greater = [i for i in array[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3])) # 需排序的数组

三、小结

  • 分治法是将问题逐步分解。使用分治法处理列表时,基线条件很可能是空数组或只包含一个元素的数组。
  • 实现快速排序时,请随机地选择用作基准值的元素。快速排序的平均运行时间为O(nlog n)。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

直接插入排序到希尔排序做的那些改进

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

3259
来自专栏糊一笑

排序算法总结与实现

写在前面 一直很惧怕算法,总是感觉特别伤脑子,因此至今为止,几种基本的排序算法一直都不是很清楚,更别说时间复杂度、空间复杂度什么的了。 今天抽空理了一下,其实感...

3039
来自专栏Bingo的深度学习杂货店

Q198 House Robber

You are a professional robber planning to rob houses along a street. Each house ...

2675
来自专栏AI派

TensorFlow修炼之道(2)——变量(Variable)

变量(Variable)是 TensorFlow 中程序处理的共享持久状态的最佳方法。与常量不同的时,常量创建后,值便无法更改,但是变量创建后 可以修改。并且修...

3134
来自专栏雨过天晴

原 Hash一致性算法实现

1403
来自专栏小白客

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

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

2724
来自专栏赵俊的Java专栏

判断字符串是否没有重复元素

1042
来自专栏desperate633

LintCode 寻找旋转排序数组中的最小值 II题目分析代码

假设一个旋转排序的数组其起始位置是未知的(比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2)。

671
来自专栏smy

js或者php浮点数运算产生多位小数的理解

image.png <?php $f = 0.58; var_dump(intval($f * 100)); //为啥输出57 ?>  首先我...

2909
来自专栏一“技”之长

经典排序算法解析 原

    许多高级语言中都提供有排序函数,但是掌握一些经典排序算法的基本原理和编码方法还是很有必要,这个学习过程可以帮助我们更好的理解每种排序算法的设计思路,本篇...

611

扫码关注云+社区