参考答案：C.首先排除怎么都是O(n2)的冒泡排序。

对快速排序，它是每次划分出小于key和大于key的2部分，继续往下排序的。对每种特定的key选择策略，我们都可以构造出一个无序序列，使得快速排序每次划分时有一个区间只有一个值，另一个区间右剩下所有值，最坏复杂度是O(n2)；
对希尔排序，他的时间复杂度最坏情况取决于所选取的步长序列，而最好的也是O(nlog2n)/O(n1.5)的；
对归并排序，先往下划分到不可再划分，之后往上合并相邻2个有序序列，层数一定是logn层，每层合并完成代价是n，所以在任何情况下时间复杂度为O(nlogn)。