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

╰半橙微兮° 2024-04-18 22:48 71阅读 0赞

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

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

![640?wx\_fmt=png][640_wx_fmt_png]

作者 | 程序员小吴

来源 | 五分钟学算法

### 题目描述 ###

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

A、快速排序

B、插入排序

C、选择排序

D、归并排序

### 题目解析 ###

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

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

![640?wx\_fmt=png][640_wx_fmt_png 1]

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

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

![640?][640]

**有热门推荐?**

1.【程序员】[全球最厉害的 14 位程序员][14]

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

3.【算法】[动画：七分钟理解什么是KMP算法][KMP]

4.【数据结构】[十大经典排序算法动画与解析，看我就够了][Link 1]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

[640_wx_fmt_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/4dd06dfda39543309db98ef6095296ac.png
[640_wx_fmt_png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/f6aa1132d3c848a6bdf626c2e0c49c53.png
[640]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/1932f390b234459fb25b36526b30591f.png
[14]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486099&idx=1&sn=6ea84944fe6a3d6dd1af2b00f3e53002&chksm=fa0e6512cd79ec04c8e8c63e74d78cc23629b88290a8e0642e5e44601f99fc39a3ea530867bc&scene=21#wechat_redirect
[GitHub]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247486254&idx=1&sn=654c208601879fe1b76c682a069a4e6a&chksm=fa0e64afcd79edb960a9863c7af7e6de5893da2326e6eca2bcd9d68061966d200ba0e189ab91&scene=21#wechat_redirect
[KMP]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485939&idx=1&sn=b25f39b5644da92c4047bbbd9936f73c&chksm=fa0e6672cd79ef64dda0a21e23c2817edf4a64cbb75b9bed328d6519c6cd4fef36d03a4cb309&scene=21#wechat_redirect
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[640_wx_fmt_jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/4eb876cdd573425390f5e6ad385d6e83.png