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