SYSTEM
算法总结
src/content/notes/system/算法总结.md 算法总结
稳定性
稳定性:在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中 r[i]=r[j],且 r[i] 在 r[j] 之前,而在排序后的序列中,r[i] 仍在 r[j] 之前,则称这种排序算法是稳定的,否则称为不稳定的
如果一组数据只需要一次排序,则稳定性一般是没有意义的,如果一组数据需要多次排序,稳定性是有意义的。
- 冒泡排序:只有当
arr[i]>arr[i+1]的时候,才会交换元素的位置,而相等的时候并不交换位置,所以冒泡排序是一种稳定排序算法 - 选择排序:是给每个位置选择当前元素最小的,例如有数据{5(1),8 ,5(2), 3, 9 },第一遍选择到的最小元素为3,所以5(1)会和3进行交换位置,此时5(1)到了5(2)后面,破坏了稳定性,所以是不稳定的排序算法
- 插入排序:比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么把要插入的元素放在相等元素的后面。相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的
- 希尔排序:按照不同步长对元素进行插入排序,虽然一次插入排序是稳定的,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以希尔排序是不稳定的
- 归并排序在归并的过程中,只有
arr[i]<arr[i+1]的时候才会交换位置,如果两个元素相等则不会交换位置,所以它并不会破坏稳定性,归并排序是稳定的 - 快速排序:快排需要一个基准值,在基准值的右侧找一个比基准值小的元素,在基准值的左侧找一个比基准值大的元素,然后交换这两个元素,此时会破坏稳定性,所以快速排序是一种不稳定的算法
记忆口诀:
-
情绪不稳定,快些选一堆好友来聊天
-
快:快速排序、些:希尔排序、选:选择排序、堆:堆排序
算法对比

补充问题
海量数据问题:
- 海量数据排序:
- 外部排序:归并 + 败者树
- 基数排序:https://time.geekbang.org/column/article/42038
- 海量数据查询:
- 布隆过滤器判断是否存在
- 构建索引:B+ 树、跳表