常见排序算法的时间复杂度和稳定性是怎样的？

参考要点

• 冒泡和插入排序稳定，平均和最坏 O(N²)，数组已经有序时只需 O(N)
• 选择排序不稳定，总是 O(N²)
• 希尔排序是改进的插入排序，不稳定，最坏约 O(N^1.5)
• 归并排序稳定，O(NlogN)，需要 O(N) 的辅助空间
• 堆排序不稳定，O(NlogN)，额外空间 O(1)，但不能利用局部性
• 快速排序不稳定，期望 O(NlogN)、最坏 O(N²)，递归栈 O(logN)，内循环指令少、顺序访问数据，是最快的通用排序
• 稳定性指相等的元素排序后保持原来的相对顺序，只交换相邻元素的冒泡、插入和相等时取左侧的归并是稳定的，远距离交换会越过相等的元素，例如选择排序把 [5a, 8, 5b, 2] 排成 [2, 5b, 5a, 8]

• 排序算法的比较