Question

哪个排序算法的平均时间复杂度不是o(nlogn)

Answer 1

快速排序算法的平均时间复杂度为O(nlogn) 。

快速排序最差情况递归调用栈高度O(n)，平均情况递归调用栈高度O(logn)，而不管哪种情况栈的每一层处理时间都是O(n)，所以，平均情况（最佳情况也是平均情况）的时间复杂度O(nlogn)，最差情况的时间复杂度为O(n^2)。

评价标准

稳定性是一个特别重要的评估标准。稳定的算法在排序的过程中不会改变元素彼此的位置的相对次序，反之不稳定的排序算法经常会改变这个次序，这是我们不愿意看到的。

我们在使用排序算法或者选择排序算法时，更希望这个次序不会改变，更加稳定，所以排序算法的稳定性，是一个特别重要的参数衡量指标依据。就如同空间复杂度和时间复杂度一样，有时候甚至比时间复杂度、空间复杂度更重要一些。

选择排序

选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。