Question

对n个记录的文件进行快速排序，所需要的辅助存储空间大致为？求解释

Answer 1

快速排序在系统内部需要一个栈来实现递归。若每次划分比较均匀，则其递归树的高度为O(logn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。

——数据结构（用C++语言描述）  北京邮电大学出版社

Answer 2

前面几个答案都是答非所问。！！
快速排序的思想是不断对待排序的元素按指定的元素进行划分，然后对两部分再进行划分……。在划分过程中，用到递归算法，其递归算法平均深度为约为 log2n，所以其空间复杂度为O(log2n)。

Answer 3

堆排序：是一种树型选择排序，特点是，在排序过程中，把R[1..n]看成是一个完全二叉树的存储结构，利用完全二叉树双亲结点和孩子结点的内在关系，在当前无序区中选择关键字最大（最小）的记录。
（2）堆排序步骤：
1、从k-1层的最右非叶结点开始，使关键字值大（或小）的记录逐步向二叉树的上层移动，最大（或小）关键字记录成为树的根结点，使其成为堆。
2、逐步输出根结点，令r[1]=r[i](i=n,,n-1,...,2)，在将剩余结点调整成堆。直到输出所有结点。我们称这个自堆顶到叶子的调整过程为“筛选”。
（3）要解决的两个问题：
1、如何由一个无序序列建成一个堆；
2、输出一个根结点后，如何将剩余元素调整成一个堆。
将一个无序序列建成一个堆是一个反复“筛选”的过程。若将此序列看成是一个完全二叉树，则最后一个非终端结点是第floor(n/2)个元素，由此“筛选”只需从第floor(n/2)个元素开始。
堆排序中需一个记录大小的辅助空间，每个待排的记录仅占有一个存储空间。堆排序方法当记录较少时，不值得提倡。当n很大时，效率高。堆排序是非稳定的。
堆排序的算法和筛选的算法如第二节所示。为使排序结果是非递减有序排列，我们在排序算法中先建一个“大顶堆”，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1个记录进行筛选，重新将它调整为一个“大顶堆”，然后将选得的一个关键字为最大的记录（也就是第一个元素）与当前最后一个记录交换（全局看是第n-1个），如此往复，直到排序结束。由到，筛选应按关键字较大的孩子结点向下进行。