选择排序：树型选择排序（稳定）

【算法思想】：首先对 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