单选题
91．设有n个结点进行排序，不稳定排序是{{U}} (1) {{/U}}；快速排序的最坏时间是{{U}} (2) {{/U}}。
单选题 (1)
【正确答案】 C
【答案解析】
单选题 (2)
【正确答案】 B
【答案解析】
[解析] 各种排序方法的性能比较如表8-1所示。

表8-1 排序方法的性能比较

排序方法
最好时间
平均时间
最坏时间
辅助时间
稳定性
直接插入
O(n)
O(n2)
O(n2)
O(1)
稳定
简单选择
O(n2)
O(n2)
O(n2)
O(1)
不稳定
冒泡排序
O(n)
O(n2)
O(n2)
O(1)
稳定
希尔排序
--
O(n1.25)
--
O(1)
不稳定
快速排序
O(n log2n)
O(n log2n)
O(n2)
O(n log2n)
不稳定
堆排序
O(n log2n
O(n log2n)
O(n log2n)
O(1)
不稳定
归并排序
O(n log2n
O(n log2n)
O(n log2n)
O(n)
稳定
基数排序
O(d(n+rd))
O(d(n+rd))
O(d(n+rd))
O(rd)
稳定

由表中可以看出，题目中提供出直接插入排序、冒泡排序和归并排序都是稳定排序。希尔排序是不稳定排序，所以，第1空的正确答案为选项C。
快速排序的最坏时间为O(n2)，对于第2空，选项B为正确答案。