单选题 排序方法的稳定性是指 ____ 。
【正确答案】 D
【答案解析】待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。注意：排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。
下表列出了各种内部排序算法的平均时间、最坏情况、辅助空间、稳定性。
排序方法
平均时间
最坏情况
辅助空间
稳定性
直接插入排序
O(n 2 )
O(n 2 )
O(1)
稳定
拆半插入排序
O(n 2 )
O(n 2 )
O(1)
稳定
起泡排序
O(n 2 )
O(n 2 )
O(1)
稳定
直接选择排序
O(n 2 )
O(n 2 )
O(1)
不稳定
希尔排序
O(n 1.3 )
O(n 1.3 )
O(1)
不稳定
快速排序
O(nlog 2 n)
O(n 2 )
O(log 2 n)
不稳定
堆排序
O(nlog 2 n)
O(nlog 2 n)
O(1)
不稳定
2—路归并排序
O(nlog 2 n)
O(nlog 2 n)
O(n)
稳定
基数排序
O(d*(rd+n))
O(d*(rd+n))
O(rd)
稳定