简单选择排序、堆排序和归并排序的时间复杂度都是O(nlogn)，且不随记录序列中关键字分布而改变。冒泡排序和插入排序在最佳情况下可以达到O(n)，但在最坏情况下会退化为O(n^2)。快速排序的时间复杂度在最坏情况下也是O(n^2)。正确答案的依据是排序算法的时间复杂度不受关键字分布影响。错误选项A、B和D的时间复杂度会随关键字分布而变化。