:-: 14.8 树形选择排序（堆排序前身） * * * * * **基本概念：** 树形选择排序（Tree Selection Sort），又称锦标赛排序（Tournament Sort），也可以算得上堆排序的前身，是一种按照锦标赛思想进行选择排序的方法。它是根据节点的大小, 建立树, 输出树的根节点, 并把此重置为最大值, 再重构树，因为树中保留了一些比较的逻辑, 所以减少了比较次数。主要流程为首先对n个记录的关键字进行两两比较，然后在其中[n/2]（取上界）个较大（小）者之间再进行两两比较，选出最大（小）数值的记录为止，取出最大（小）数值，将其设为maxValue，重复上面，选出次大（小）数值。 **算法的运作** 1、首先对n个记录进行两两比较，得到较小的n/2个数再依次比较，依次类推直到得到一个最小值,这是一个构造完全二叉树的过程，根节点即为最小元素，叶子节点为列表元素。构造的此树的存储结构可以用数组表示方法，数组长度为2n-1。填充此树，比如列表元素为：8 4 12 7 35 9 22 构造的树为： :-:  4为根结点位最小值，列表元素为叶子节点 2、移走最小元素，此时可重新为数组a的第一个位置赋值为此最小值， 之后如果找出次小值则可以为第二个位置赋值，...... 3、找出次小值，找出最小值在叶子节点的位置，从该节点开始，和其兄弟节点，进行比较，修改从叶子节点到根节点的元素值，比较完毕后，根节点为次小值。（第三步比较是利用了第一次比较提供的信息，因为第一步已经得到了两两比较的较小值，只要拿第一次与最小值比较的元素(即最小值的兄弟节点)与它们比较即可得最小值。 ） 4、重复第二和第三步，排序完成。 **图片示例：** :-:  :-:  :-:  :-:  **代码实现：** ~~~ public static void treeSelectSort(Object[] a) { int len = a.length; int treeSize = 2 * len - 1; // 完全二叉树的节点数 int low = 0; Object[] tree = new Object[treeSize]; // 临时的树存储空间 // 由后向前填充此树，索引从0开始 for (int i = len - 1, j = 0; i >= 0; --i, j++) { // 填充叶子节点 tree[treeSize - 1 - j] = a[i]; } for (int i = treeSize - 1; i > 0; i -= 2) { // 填充非终端节点 tree[(i - 1) / 2] = ((Comparable) tree[i - 1]).compareTo(tree[i]) < 0 ? tree[i - 1] : tree[i]; } // 不断移走最小节点 int minIndex; while (low < len) { Object min = tree[0]; // 最小值 a[low++] = min; minIndex = treeSize - 1; // 找到最小值的索引 while (((Comparable) tree[minIndex]).compareTo(min) != 0) { minIndex--; } tree[minIndex] = Integer.MAX_VALUE; // 设置一个最大值标志 // 找到其兄弟节点 while (minIndex > 0) { // 如果其还有父节点 if (minIndex % 2 == 0) { // 如果是右节点 tree[(minIndex - 1) / 2] = ((Comparable) tree[minIndex - 1]).compareTo(tree[minIndex]) < 0 ? tree[minIndex - 1] : tree[minIndex]; minIndex = (minIndex - 1) / 2; } else { // 如果是左节点 tree[minIndex / 2] = ((Comparable) tree[minIndex]).compareTo(tree[minIndex + 1]) < 0 ? tree[minIndex] : tree[minIndex + 1]; minIndex = minIndex / 2; } } } } ~~~ **复杂度分析：** 时间复杂度：O(nlogn)。 空间复杂度：O(n)。 为什么时间复杂度降低了？ 第一趟的比较是可以为后续的比较提供信息的，使后续的比较次数大大减少， 而后续的比较又可以为更后续的比较提供信息，这样就减少了比较的次数，减小了时间复杂度。 **怎么根据列表元素确定所有节点的个数？** 列表中的所有元素都是叶子节点,假设有n个元素，也就是有n个叶子节点，所以假设高度为h,2^h-1 = n,所以有2h = 2n,对于满二叉树，节点数为2h - 1 = 2n - 1。又已知叶子节点个数为n。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。** **本文主要参考以下文章：** [数据结构排序ppt：提取码：270s](https://pan.baidu.com/s/10WWKUT-VQZ2foCfhIWWMSQ) [数据结构——树形选择排序](http://blog.51cto.com/13022101/2142664) [树形选择排序](https://www.cnblogs.com/mengdd/archive/2012/11/27/2791412.html) [选择排序(树形排序，堆排序）这个堆排序有错误](http://zhouyunan2010.iteye.com/blog/1217462)