Question

冒泡排序,堆排序,快速排序,插入排序,归并排序的的稳定性及时间空间复...

Answer 1

1、冒泡排序、直接插入排序、二分插入排序、归并排序，基数排序都是稳定排序。不稳定排序：直接选择排序、堆排序、快速排序、希尔排序，猴子排序。以升序为例，比较相邻的元素，如果第一个比第二个大，则交换他们两个。

2、归并排序是稳定的排序算法。归并排序的稳定性分析：归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素或者2个序列，然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。

3、其中插入排序，冒泡排序是简单排序，排序的平均时间复杂度是O（n^2），最坏的情况是O(n^2)，辅助存储空间是O(1)。

4、堆排序、快速排序、希尔排序、直接选择排序不是稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。