Question

下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是__________。

A、堆排序 B、起泡排序
C、直接选择排序 D、快速排序

Answer 1

这个首先要明确一点，只用到比较的排序算法最低时间复杂度是O(nlogn)，而像桶排这样的只需要O(R)(R为桶的大小)
为了证明只用到比较的排序算法最低时间复杂度是O(nlogn)，首先要引入决策树。
首先决策树是一颗二叉树，每个节点表示元素之间一组可能的排序，它予以京进行的比较相一致，比较的结果是树的边。
先来说明一些二叉树的性质，令T是深度为d的二叉树，则T最多有2^片树叶。
具有L片树叶的二叉树的深度至少是logL。
所以，对n个元素排序的决策树必然有n!片树叶（因为n个数有n!种不同的大小关系），所以决策树的深度至少是log(n!)，即至少需要log(n!)次比较。
而
log(n!)=logn+log(n-1)+log(n-2)+...+log2+log1
>=logn+log(n-1)+log(n-2)+...+log(n/2)
>=(n/2)log(n/2)
>=(n/2)logn-n/2
=O(nlogn)
所以只用到比较的排序算法最低时间复杂度是O(nlogn)。

Answer 2

冒泡排序的时间复杂度为O（n^2）,经过改进的冒泡排序时间复杂度受初始数据影响,最优为O(n),最差仍为O(n^2)
选择排序为O(n^2)
快速排序平均复杂度为O(nlog2(n)),最差为O(n^2)(受数据影响时)
堆排序的最坏时间复杂度为O(nlog2(n)),平均复杂度趋近于最坏复杂度
那么答案应该是选择排序