【正确答案】排序方法平均时间最坏情况辅助空间稳定性不稳定排序举例 直接插入排序O（n2）O（n2）O（1）稳定 折半插入排序O（n2）O（n2）O（1）稳定 二路插入排序O（n2）O（n2）O（n）稳定 表插入排序O（n2）O（n2）O（1）稳定 起泡排序O（n2）O（n2）O（1）稳定 直接选择排序O（n2）O（n2）O（1）不稳定2,2’,1 希尔排序O（n1.3）O（n1.3）O（1）不稳定3,2,2’,1(d=2,d=1) 快速排序O（nlog2n）O（n2）O（log2n）不稳定2,2’,1 堆排序O（nlog2n）O（nlog2n）O（1）不稳定2,1,1’(极大堆) 2-路归并排序O（nlog2n）O（nlog2n）O（n）稳定 基数排序O ( d*(rd+n) )O ( d*(rd+n) )O (rd )稳定