Question

在插入排序、冒泡排序、快速排序、归并排序等排序算法中,占用辅助空间最多的是哪个？

Answer 1

在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用辅助空间最多的是归并排序。

对n个记录的文件进行快速排序，所需要的辅助存储空间大致为O(1og2n)。

1、所有的简单排序方法（包括：直接插入、起泡和简单选择）和堆排序的空间复杂度为O(1)；

2、快速排序为O(logn)，为栈所需的辅助空间；

3、归并排序所需辅助空间最多，其空间复杂度为O(n)；

4、链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)。

扩展资料

计算机排序算法的特点

1、有穷性

一个算法应包含有限的操作步骤，而不能是无限的。有穷性值在合理范围之内，如果让计算机执行一个历时1000年才结束的算法，这虽然是有穷的，但超过了合理的限度，人们不把他视为有效算法。

2、确定性

算法中的每一个步骤都应当是确定的，而不应当是含糊的，摩棱两可的。算法中的每一个步骤应当不致被解释成不同含义的，而应是十分明确的。也就是说，算法的含义应当是唯一的，而不应当产生歧义性。

3、有零个或多个输入

所谓输入，即在执行算法是需要从外界取得必要的信息。

4、有一个或多个输出

算法的目的是为了求解，没有输出的算法是没有意义的。

5、有效性

算法中的每一个步骤都应当能有效的执行，并得到确定的结果。

Answer 2

是《数据结构》课上的吧？。。。呵呵。。。

直接插入排序是将一个记录插入已排序好的序表中，从而得到一个新的、记录增1的有序序列。它需要设置一个哨兵，通常就是用R[0]，所以它需要的辅助空间为1。

冒泡排序主要是利用相邻大小比较之后的交换实现的，在交换的时候需要一个辅助空间，所以它需要的辅助空间也为1。事实上，冒泡排序是快速排序的一种特例。

快速排序中除了交换时需要一个数据的辅助空间。

归并排序归并排序主要是分治的思想，即把两个或两个以上的有序表合成一个新的有序表，实现归并排序需要和待排记录等数量的辅助空间。

Answer 3

必然是归并，归并并不是就地排序，而其他三个都是。
也就是说，其他三个都将占用常数个辅助空间，而归并在执行时会占用O(n)的空间进行辅助排序，而其他都是O(1)。

Answer 4

插入排序、冒泡排序都是O(n^2)的
快速排序、归并排序是 O(n*log2(n))的
一般情况下，快速的排序方式都是以牺牲空间为代价的....
而相比而言，归并排序使用的辅助空间最多，因为它要对多个链表排序，还要合并，都要附属空间，但快速排序只要一个一个链表....

Answer 5

好像是归并排序