点击蓝色“五分钟学算法”关注我哟

加个“星标”,天天中午 12:15,一起学算法

【系列】经典算法题 :排序算法空间

作者 | 程序员小吴

来源 | 五分钟学算法

题目描述

下述几种排序方法中,要求内存最大的是()

A、快速排序

B、插入排序

C、选择排序

D、归并排序

题目解析

一般对于 排序问题 ,我们遇到的都是考察 时间复杂度 ,很少会去了解它们的 空间复杂度,险些被这道题给绕过去。

这个问题如果对下面这张图比较了解的话,很快就能选出答案。

【系列】经典算法题 :排序算法空间

  • 快速排序的实现采取了递归,因此空间复杂度为 O(logn)。

  • 插入排序只是借助一个临时变量进行交换元素,因此空间复杂度为 O(1)。

  • 选择排序与插入排序差不多,因此空间复杂度为 O(1)。

  • 归并排序需要分配一个大小为 n 的数组,因此空间复杂度为 O(n)。

所以,这一题的答案为 D。

【系列】经典算法题 :排序算法空间

有热门推荐?

1.程序员全球最厉害的 14 位程序员

2.【GitHub我在 GitHub 上看到了一个丧心病狂的开源项目!

3.【算法动画:七分钟理解什么是KMP算法

4.【数据结构十大经典排序算法动画与解析,看我就够了!

【系列】经典算法题 :排序算法空间