计算机排序的空间复杂度如何？

Question

如题所述

Answer 1

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

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

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

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

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

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

扩展资料

计算机排序算法的特点

1、有穷性

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

2、确定性

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

3、有零个或多个输入

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

4、有一个或多个输出

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

5、有效性

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