选择排序：树型选择排序（稳定）
【算法思想】：首先对 n 个记录的关键字进行两两比较，然后在其中 不大于 n/2 的整数个较小者之间再进行两两比较，直到选出最小关键字的记录为止。可以用一棵有 n 个叶子结点的完全二叉树表示。
树形选择排序图解如下：
图片来自网络
1、对 n 个关键字两两比较，直到选出最小关键字为止，一趟排序结束
图片来自网络
2、反复这个过程，仅需将叶子结点的最小关键字改为最大值∞，即可
图片来自网络
3、然后从该叶子结点开始，继续和其左右兄弟的关键字比较，找出最值
图片来自网络
图片来自网络
图片来自网络
图片来自网络
图片来自网络
图片来自网络
图片来自网络
注：
时间复杂度：由于含有 n 个叶子结点的完全二叉树的深度为图片来自网络 ，则在树形选择排序中，除了最小关键字外，每选择一个次小关键字仅需进行
图片来自网络
次比较，故时间复杂度为 O(n logn)。
缺点： 1、与“∞”的比较多余； 2、辅助空间使用多。
为了弥补这些缺点，1964年，堆排序诞生。
[参考文献]https://www.cnblogs.com/kubixuesheng/p/4359406.html
image.png
网友评论