以下哪种排序算法需要开辟额外的存储空间？_京东笔试题

MyGoodHelper

B

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

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

发表于 2015-01-18 21:30:16 回复(0)

推荐

张家不二君

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

编辑于 2015-01-31 11:31:00 回复(5)

郭海旭

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

发表于 2016-03-15 01:36:05 回复(0)

coco酱是个程序媛哟

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

* 桶排序（ 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) 额外空间

发表于 2015-08-10 15:16:58 回复(0)

DBest

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

发表于 2018-02-07 22:38:35 回复(0)

nomico271

归并排序需要空间复杂度为O（n）；
堆排序为O（1）；
快排为O（logn）

发表于 2017-08-04 12:04:35 回复(0)

牛客-007

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

发表于 2015-01-28 17:38:52 回复(1)

菩提旭光

概念： 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

特点： 归并排序的最好、最坏和平均时间复杂度都是 O(nlogn) ，而空间复杂度是 O(n)， 比较次数介于(nlogn)/2和(nlogn)-n+1，赋值操作的次数是(2nlogn)。

点评： 归并排序算法比较占用内存，但却是效率高且稳定的排序算法。

发表于 2015-08-22 10:40:44 回复(1)

codermanFans

这一题的隐含条件肯定是需要额外存储空间最大的，因为每个排序算法都需要额外的存储空间，除非在交换的时候不使用临时变量。

发表于 2015-08-21 20:00:13 回复(1)

ridikuius

B

稳定排序：

* 泡沫排序（ bubble sort ） — O(n²)
* 插入排序（ insertion sort ） — O(n²)
* 桶排序（ 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) 额外空间
.
不稳定排序
* 选择排序（ selection sort ） — O(n²)
* 希尔排序（ shell sort ） — O(n log n) 如果使用最佳的现在版本
* 堆排序（ heapsort ） — O(n log n)
* 快速排序（ quicksort ） — O(n log n) 期望时间 , O(n2) 最坏情况 ; 对于大的、乱数串行一般相信是最快的已知排序

发表于 2015-09-23 09:30:27 回复(0)

jiangyubo

快速排序也需要开辟额外空间吧

发表于 2015-08-21 09:55:48 回复(0)

阳光下的米雪

快排不是也需要，还分好几种情况

发表于 2019-04-28 18:13:21 回复(0)

梅老板

是不是问的是谁占用的最大呀

发表于 2022-03-05 16:18:50 回复(0)

牛客小妞号

归并排序是将两个已有序的子序列合并，得到完全有序的序列。
它的时间复杂度最好最坏和平均都为nlogn，空间复杂度为n。
它是一个比较占用内存，但效率较高且文档的算法。

发表于 2021-06-03 13:05:26 回复(0)

梦境迷离

不严谨

发表于 2017-12-16 00:33:08 回复(0)

黏黏糖

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

发表于 2017-06-26 16:50:18 回复(0)

假装路过_

难道快速排序不需要额外空间！

发表于 2017-05-26 12:13:25 回复(0)

Andone1cc

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

发表于 2016-09-20 17:47:27 回复(0)

Hi_Man

感觉表述不清楚啊

发表于 2016-08-24 20:53:18 回复(0)

wentguo

这里说的开辟额外的存储空间应该是堆空间，不是栈空间

发表于 2016-04-22 21:49:05 回复(0)

DD小样

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

*  桶排序（ 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)  额外空间

概念：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

特点： 归并排序的最好、最坏和平均时间复杂度都是 O(nlogn) ，而空间复杂度是 O(n)，比较次数介于(nlogn)/2和(nlogn)-n+1，赋值操作的次数是(2nlogn)。

点评：归并排序算法比较占用内存，但却是效率高且稳定的排序算法。

发表于 2015-08-27 20:46:02 回复(0)

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

问题信息

热门推荐

相关试题