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

软件环境: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 条评论
登录 后参与评论

相关文章

来自专栏转载gongluck的CSDN博客

python笔记:#007#变量

变量的基本使用 程序就是用来处理数据的,而变量就是用来存储数据的 目标 变量定义 变量的类型 变量的命名 01. 变量定义 在 Python 中,每个变量 在...

3178
来自专栏JavaEE

Java面试题-01前言:面试题:总结:

1625
来自专栏happyJared

设计模式入门:抽象工厂模式

  抽象工厂用于提供创建一系列相关或互相依赖的接口,而无需指定它们具体的类。对比工厂方法,抽象工厂面对的是整个产品族,而工厂方法面对的是独立的产品。

751
来自专栏noteless

[一] java8 函数式编程入门 什么是函数式编程 函数接口概念 流和收集器基本概念

说起来好像很啰嗦,但是如果有人告诉你 通过sin(x) 计算后, x的值被改变了,你不会觉得异常奇怪么

822
来自专栏诸葛青云的专栏

C语言夺命题十例,为啥C语言的总是这么恶趣味?

这些问题测试了C语言的高级知识,包括一些很少使用的特性。有效的C编程需要对诸如未定义的行为,递归和指针算术等概念有深入的理解,但是这些故意复杂的例子并不代表现实...

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

【Java提高四】接口与抽象类

【Java提高四】接口与抽象类 接口和内部类为我们提供了一种将接口与实现分离的更加结构化的方法。 抽象类与接口是java语言中对抽象概念进行定义的...

3416
来自专栏Java编程

10个有关String的面试问题

下面是面试中最容易问到的有关String的问题。

1K2
来自专栏章鱼的慢慢技术路

《算法图解》第四章笔记与课后练习

1635
来自专栏C++

python笔记:#007#变量

762
来自专栏追不上乌龟的兔子

介绍一些Python str类的方法

上面的代码正确的返回了'0.333333',但是当x = 1 / 2时,由于小数只有一位,这个方案的结果就是'0.5'了,而不是预期中的'0.500000'。

914

扫码关注云+社区