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

• 2019 年 10 月 4 日
• 筆記

作者 | 程序员小吴

来源 | 五分钟学算法

题目描述

下述几种排序方法中，要求内存最大的是（）

A、快速排序

B、插入排序

C、选择排序

D、归并排序

题目解析

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

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

• 快速排序的实现采取了递归，因此空间复杂度为 O(logn)。
• 插入排序只是借助一个临时变量进行交换元素，因此空间复杂度为 O(1)。
• 选择排序与插入排序差不多，因此空间复杂度为 O(1)。
• 归并排序需要分配一个大小为 n 的数组，因此空间复杂度为 O(n)。

以，这一题的答案为 D。