Question

时间复杂度为O(n^2)的几种排序

Answer 1

1.最好，最坏，平均时间复杂度。
2.比较次数和交换次数。
3.时间复杂度的系数，常数，低阶。

空间复杂度为O(1) 的排序算法。

相等元素排序之后原有顺序不变。
case:
比如我们有一组数据 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。这组数据里有两个 3。经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。

code

空间复杂度为 O(1)

在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

时间复杂度（执行最多的单元执行的次数）。
最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

这里提供另一个分析时间复杂度的角度：

分析逆序度（定量分析）
逆序度 = 满有序度 - 有序度

有序度：
有序元素对：a[i] <= a[j], i < j。
有序度是数组中具有有序关系的元素对的个数。

code

空间复杂度为 O(1)

在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

以上写法，最佳情况O(n2)，并不是O(n)
改成如下这样写更加清晰。

code

空间复杂度为 O(1)

比如 5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。

最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)