Question

选择排序和堆排序

Answer 1

最近了解到了hadoop中的merge过程，其中使用到了外部排序。
因此总结一下选择排序和堆排序：
选择排序 ：选择排序的时间复杂度为O(n^2);不需要额外的存储空间。也就是简单选择排序。
就是每次选出来一个最小值，和第一个元素交换；第二轮再选未排序队列中的最小值。。。
'''

'''
树形选择排序 的优点是，相较于简单选择排序，是和中间结果比较，减少了比较的次数。树形选择排序只有叶子节点是待排序列，中间结点是排序的中间结果。

外部排序中：多路归并排序+败者树（用到了内存中的归并排序（分治法，divide and conquer）+外部的多路归并排序，多路归并的限制因素是外部磁盘的访问次数，虽然多路减少了磁盘的读写次数，但是多路的极值比较增多，抵消掉多路归并中磁盘读写带来的性能提升，因此采用败者树）

败者树：是一种完全二叉树，是 树形选择排序 的变种。 只有叶子节点是待排序的。中间节点是排序的中间结果。
选择排序（O（n^2））-->树形选择排序(额外的存储空间较大)--> 堆排序

堆排序： 所有的节点都是待比较的数据 。
大顶堆和小顶堆：
每个节点都大于或者等于左右孩子结点的值，称为大顶堆；
每个节点都小于或者等于左右孩子节点的值，成为小顶堆；

并且，堆是完全二叉树，因此可以用数组来进行存储。

以前学这些，因为没有具体的应用场景，不是很理解，每次看完就忘。