专栏首页五分钟学算法【系列】经典算法题 :排序算法空间

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

作者 | 程序员小吴

来源 | 五分钟学算法

题目描述

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

A、快速排序

B、插入排序

C、选择排序

D、归并排序

题目解析

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

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

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

以,这一题的答案为 D。

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员小吴

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-12

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 五分钟学算法之经典算法题 :排序算法(某东算法工程师比赛)

    已知数据表 A 中每个元素距其最终位置 不远 ,为了节省时间,应该采取的算法是()

    五分钟学算法
  • 独乐乐不如众乐乐,如何装逼的求众数

    今天分享的题目来源于 LeetCode 上第 169 号问题:求众数(求数组中超过一半的数字)。题目难度为 Easy,目前通过率为 45.8% 。

    五分钟学算法
  • 十大经典排序算法动画,看我就够了!

    Tip 为了演示更加清楚,本文中所有的动画都放慢了速度,因此GIF大小对比之前会有所增大,图片加载速度会变慢,如果你想获取所有的超清动画,在公众号回复 腾讯 可...

    五分钟学算法
  • 面试前你必须知道的三个排序算法

    今天分享的是三种排序算法,在面试、实际编程中经常会碰到和使用到的,我会带领大家从分析排序算法技巧上以及代码实现上全面理解这一知识点的掌握。

    用户1093975
  • 动画:面试官问我插入排序和冒泡排序哪个更牛逼?

    排序对于每个开发者来讲,都多多少少知道几个经典的排序算法,比如我们之前以动画形式分享的冒泡排序,也包括今天要分享的插入排序。还有一些其他经典的排序,小鹿整理的共...

    小白学视觉
  • 算法:插入排序(InsertSort)

    每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

    WEBJ2EE
  • 详解排序算法--插入排序和冒泡排序插入排序和冒泡排序分析

    冒泡排序(英语:Bubble Sort,台湾另外一种译名为:泡沫排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把...

    desperate633
  • AI_第一部分 数据结构与算法(10.排序简介)

    第四阶段我们进行深度学习(AI),本部分(第一部分)主要是对底层的数据结构与算法部分进行详尽的讲解,通过本部分的学习主要达到以下两方面的效果:

    还是牛6504957
  • 必须掌握的八种排序(1-2)--插入排序,希尔排序

    很多人算法和数据结构不好,归根结底就是基础不扎实,算法和数据结构不好的话,达到的高度肯定不会很高,最近重新加强了一下自己的算法基础,决定从最基础的内容开始,如有...

    汤高
  • Python|冒泡排序

    外排序 :由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;

    Rare0716

扫码关注云+社区

领取腾讯云代金券