题4
题目
Q:下列排序算法中属于稳定排序的是 (冒泡排序，直接插入排序，归并排序)
平均时间复杂度为
在最好的情况下, 时间复杂度可以达到线性时间的有 (冒泡排序，归并排序). (注: 多选题)
I. 冒泡排序
II. 堆排序
III. 选择排序
IV. 直接插入排序
V. 希尔排序
VI. 归并排序
VII. 快速排序
分析
A:堆排序肯定是不稳定的
归并排序肯定是稳定的
快排是不稳定的，因为快排是基于和“基准”比较得到的，划分的时候，可能会导致相同的元素位置发生变化
希尔排序是插入排序的改进，通过提前划分分组，然后对每个分组进行插入排序，所以希尔排序是不稳定的，这个不稳定性是划分分组导致的
插入排序本身是稳定的，因为插入排序是通过比较相邻元素的大小，然后插入到合适的位置，所以相同元素的位置不会发生变化
简单选择排序和堆排序都是选择排序，因为存在选择交换的过程，所以不稳定
冒泡排序是稳定的，因为比较的是相邻元素的相对大小，所以相同元素的位置不会发生变化，也就是说相邻元素的相对大小不会导致交换
解
① I、IV、VI
② II、VI、VII
③ I、IV
读者应能从算法的原理上理解算法的稳定性情况。堆排序和归并排序在最坏情况下的时间复杂度与最好情况下的时间复杂度是同一数量级的,都是