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

题目

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

A.选择排序

B.归并排序

C.快速排序

D.堆排序

解答

正确答案是 B

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

C 14条回复评论

落地成盒

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

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

虹猫

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

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

雪糕乐

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

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

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

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