class 029 重要排序算法的总结
这篇文章是看了“左程云”老师在b站上的讲解之后写的, 自己感觉已经能理解了, 所以就将整个过程写下来了。
这个是“左程云”老师个人空间的b站的链接, 数据结构与算法讲的很好很好, 希望大家可以多多支持左程云老师, 真心推荐.
https://space.bilibili.com/8888480?spm_id_from=333.999.0.0
1. 常见排序算法的稳定性
稳定性：能不能在拍完序之后, 让相同的值保持原来的次序.
比如：arr[] = {3, 4, 2, 3, 1}, 排序之后一定是：1, 2, 3, 3, 4, 但是在原来的数组中, 第一个数字 3 的下标是：0, 第二个 3 的下标是：3, 那排序之后, 0位置下标的 3 能不能在 3位置的下标 3 之前, 要是能, 说明这个排序算法具有稳定性, 要是没有, 说明这个算法没有稳定性.
每一个排序的稳定性, 左程云老师在视频中说的非常非常清楚, 也是将每一个排序的过程串了一遍, 自己要是忘了, 可以去以前的帖子中找一下过程, 然后自己分析一遍.
上图中已经将所有比较重要的排序算法的时间复杂度, 空间复杂度和稳定性进行了总结.
2. 常见排序算法的总结
冒泡排序, 选择排序, 插入排序中, 最差的是选择排序, 因为付出了 O(n^2) 的时间复杂度, 也没有稳定性.
归并排序, 随机快速排序, 堆排序中, 最需要注意的是随机快速排序, 因为随机快速排序的时间复杂度是根据期望确定的, 不能用最差和最好的情况进行确定, 这一点在以前随机快排的帖子中有详细的说明.
