试题-以下哪种排序算法需要开辟额外的存储空间（）

题目

以下哪种排序算法需要开辟额外的存储空间（）

A.选择排序

B.归并排序

C.快速排序

D.堆排序

上一题 下一题

解答

正确答案是 B

归并算法基本操作是合并两个已经排序的表，因为这两个表是已经排序的，所以若将输出放到第三个表中则该算法可以通过对输入数据一趟排序来完成，因此是需要额外存储空间的

C 14条回复评论

骊山语罢

中枪，我脑子里全是错误回答

发表于 2021-09-13 16:15:00

0 0

希望找回我家的猪

终于弄懂这个知识点了！！！

发表于 2021-09-13 16:10:00

0 0

瀑布的背后

在卷的地方，测试要比开发还要开发，又要懂业务又要懂测试，还要懂运维，我都搞不懂现在测试到底是个什么角色了

发表于 2021-09-12 09:35:00

0 0

皮皮鲁

归并排序和快排都需要开辟额外的空间，只不过归并排序的空间复杂度为O（n）,快速排序的空间复杂度为O（logn）

发表于 2018-10-13 11:28:36

0 0

遇见

归并排序需要进行归并操作，需要归并数组，即开辟额外的存储空间。而快排的额外存储是由于递归深度引起的，辅助空间存储在O(logn)-O(n)之间，每趟快排辅助的空间存储也是一个临时单元，并不需要额外开辟。

发表于 2018-10-13 11:28:25

0 0

遇见

这题主要考察的应该是原地排序的概念。原地排序就是指不申请多余的空间来进行排序，就是在原来的排序数据中比较和交换的排序。希尔排序、冒泡排序、插入排序、选择排序、快速排序、堆排序都属于原地排序。归并排序中一个很重要的部分是两个已排序序列合并的过程，这里需要另外开辟一块新的空间来作为存储这两个已排序序列的临时容器，它并不是原地排序。

发表于 2018-10-13 11:28:09

0 0

落地98K

归并排序是一个递归的问题，采用分治的思想实现，需要额外的空间来存储临时数据。

这个算法的基本操作是合并两个已经排序的表，因为这两个表是已经排序的，所以若将输出放到第三个表中则该算法可以通过对输入数据一趟排序来完成。基本的合并算法是取两个输入数组A和B，一个输出数组C以及3个计数器(Actr、Bctr、Cctr)，他们开始于对应数组的开始端，A[Actr]和B[Bctr]的较小者复制到C[ctr]中的一下一个位置，相关的计数器向前推进一步，当两个输入表有一个用完，则将另一个表中剩余的部分拷贝到C中。

发表于 2018-10-13 11:27:53

0 0

老干妈拌面

归并排序需要开辟一个跟原数组一样大小的存储空间，不断将短的有序序列合并为长的有序序列。最终达到整个序列有序

发表于 2018-10-13 11:27:36

0 0

小洁癖

需要额外空间的排序算法：

* 桶排序（ bucket sort ） — O(n); 需要 O(k) 额外空间
* 计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外空间
* 合并排序（ merge sort ） — O(n log n); 需要 O(n) 额外空间
* 二叉排序树排序（ Binary tree sort ） — O(n log n) 期望时间 ; O(n²) 最坏时间 ; 需要 O(n) 额外空间
* 基数排序（ radix sort ） — O(n·k); 需要 O(n) 额外空间

发表于 2018-10-13 11:27:26

0 0

碧海问舟

归并排序和快排都不需要额外创建数组对象存储数据，也就是不占用堆内存。两者占用的额外存储空间来自调用递归函数时占用的栈内存。因此，快排和归并排序都需要额外的存储空间。包括用递归实现的堆排序同样

发表于 2018-10-13 11:27:12

0 0

问题信息

分类：数据结构 - 归并排序

难度:

最新校招难题刷题，快来进刷题群吧