选择排序&归并排序&基数排序
时间：2021-07-02 23:05:11
收藏：0
阅读：50
---
Selection Sort
”选择排序 “
”每一趟将待排序的最小元素（或最大元素）加入有序子序列 “
简单选择排序
算法实现
性能分析
Heap Sort
”堆排序 “
在回顾一下6.006中对与堆的定义，
结合之前学到的二叉树的顺序存储就不难理解了
”堆是一个顺序存储的完全二叉树“
了解了大根堆和小根堆的定义后，再回来看选择排序的核心思路：
”每一趟将待排序的最小元素（或最大元素）加入有序子序列 “
显然，如果我们已经拥有了一个大根堆/小根堆，上述的选择操作自然就变得十分简单，无非是取根结点的元素罢了，那么如何构造大根堆/小根堆呢？
Build a Max_heap
代码解释
- HeadAdjust函数会将以k为根的子树调整为大根堆，其使用前提是A[k]的左右子树已经是大根堆！
- i=2*k指向结点k的左孩子，if( i<len&&A[i]<A[i+1] ) i++;会使 i 指向k的左右孩子中较大的那个
- 一次循环内实际上只针对两个结点处理：父结点A[k]和较大的那个子结点A[i]，而不必考虑更下层的结点 ——（分治）
- BuildMaxHeap的调整顺序是从后往前，这十分重要! 因为这对应到逻辑图便是从下往上调整，稍微思考一下不难发现，从下往上的处理顺序可以保证在开始处理某个结点A[k]时，它的左右子树均已经是大根堆（叶子节点可以看作是特殊的大根堆 /小根堆），这也是6.006中强调的single violation，其同时也保证了上一条所述（分治）的正确性
- 由于一次循环可能会破坏以A[i]为根的子树的大根堆性质，因此如果这次循环后发生了结点调整，则使k指向发生变动的那颗子树（所谓的“下沉”），开始下一次循环判断这棵子树还是不是大根堆
基于大根堆进行排序
既然已经知道了如何构造大根堆，那么利用它进行排序就十分简单了：
- 将根节点A[1]与末尾结点A[len]互换，--len，表示待排序的元素个数减一
- 调用HeadAdjust（A，1，len）将堆调整为大根堆 （思考：为什么不用BuildMaxHeap（A，len）？）
重复上述步骤直至元素有序
性能分析
关键在于 “下坠 ”过程，即分析 HeadAdjust函数：
link：https://www.cnblogs.com/potofsalt/p/14773949.html#heap_sort
“堆排序不具有稳定性 ”
小结
堆的插入删除
插入新结点
”Now I‘m rising “
删除一个结点
”when i was drowning“
”考试有时会考关键字的比较次数 “
Merge Sort
”归并排序 ”
”与前述的交换、选择等排序思想不一样，归并的含义是将两个或两个以上的有序表组合成一个新的有序表 “
二路归并：将两个有序表合并为一个新的有序表
“内部排序中一般采用二路归并 ”
算法实现
“归并 ”
“归并排序 ”
性能分析
小结
Radix Sort
“基数排序 ”
“要求能够手动模拟排序过程 ”
性能分析
”收集 Q[i]上的所有元素的时间复杂度为O(1)，因为只需将Q[i]的 front指针赋给表尾指针 p的 next即可 “
Application
小结
原文：https://www.cnblogs.com/potofsalt/p/14964663.html
评论（0）