在插入排序、冒泡排序、快速排序、归并排序等排序算法中,占用辅助空间最多的是归并排序。
对n个记录的文件进行快速排序,所需要的辅助存储空间大致为O(1og2n)。
1、所有的简单排序方法(包括:直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1);
2、快速排序为O(logn),为栈所需的辅助空间;
3、归并排序所需辅助空间最多,其空间复杂度为O(n);
4、链式基数排序需附设队列首尾指针,则空间复杂度为O(rd)。
扩展资料
计算机排序算法的特点
1、有穷性
一个算法应包含有限的操作步骤,而不能是无限的。有穷性值在合理范围之内,如果让计算机执行一个历时1000年才结束的算法,这虽然是有穷的,但超过了合理的限度,人们不把他视为有效算法。
2、确定性
算法中的每一个步骤都应当是确定的,而不应当是含糊的,摩棱两可的。算法中的每一个步骤应当不致被解释成不同含义的,而应是十分明确的。也就是说,算法的含义应当是唯一的,而不应当产生歧义性。
3、有零个或多个输入
所谓输入,即在执行算法是需要从外界取得必要的信息。
4、有一个或多个输出
算法的目的是为了求解,没有输出的算法是没有意义的。
5、有效性
算法中的每一个步骤都应当能有效的执行,并得到确定的结果。