指的是排序过程中所需的辅助空间大小。
1. 所有的简单排序方法（包括：插入、起泡和选择排序）和堆排序的空间复杂度均为O (1)。
2. 快速排序为O (logn)，为递归程序执行过程中栈所需的辅助空间。
3. 归并排序和基数排序所需辅助空间最多，其空间复杂度为O (n)。
1. 稳定的排序方法指的是，对于两个关键字相等的记录在经过排序之后，不改变它们在排序之前在序列中的相对位置。
2. 除希尔排序、快速排序和堆排序是不稳定的排序方法外，本章讨论的其它排序方法都是稳定的。例如：对关键字序列(41,3,42,2)进行快速排序，其结果为(2,3,42,41)。
3. "稳定性"是由方法本身决定的。一般来说，排序过程中所进行的比较操作和交换数据仅发生在相邻的记录之间，没有大步距的数据调整时，则排序方法是稳定的。如本章10.4.1节中的选择排序算法没有满足"稳定"的要求是因为，每趟在右部无序区找到最小记录后常要跳过很多记录进行交换调整。显然若"交换调整"的方式改一改就能写出稳定的选择排序算法。而对不稳定的排序方法，不论其算法的描述形式如何，总能举出一个说明它不稳定的实例来。
综合上述，可得右侧列表结果。
