稳定性分析
稳定排序算法不会在排序后改变相等键值记录间的相对次序。
冒泡排序
交换逆序的相邻关键字
时间复杂度:$O(n^2)$
改进策略1:设置标志位,若某一轮没有发生交换,则排序结束 改进策略2:第i次遍历范围为0~N-i
插入排序
讲一个记录插入到有序表中,在基本良序的表中性能更好。
时间复杂度:$O(n^2)$
选择排序
第i次在 i~n的范围内寻找最小值,并放置在第i个位置处。
时间复杂度:$O(n^2)$
希尔排序
归并排序
利用分治思想对两个良序数组合并。可以快速解决逆序对相关问题。
时间复杂度:$O(nlogn)$
空间复杂度:$O(n)$ 需要辅助空间帮助合并过程
堆排序
堆是一种特殊的完全二叉树
- 大顶堆:父节点大于等于子节点
- 小顶堆:父节点小于等于子节点 应用:$O(nlogk)$复杂度解决前k个最大值问题
快排
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。时间复杂度为O(nlogn) 应用:快速解决求第k大的值问题。