各种排序的辅助空间问题

稳定性比较

 

 

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

 

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

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

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

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