漫画：什么是 “锦标赛排序” ？

野性酷女 2022-11-06 05:53 217阅读 0赞

![format_png][]

![format_png 1][]

**—————  第二天  —————**

![format_png 2][]

![format_png 3][]

![format_png 4][]

![format_png 5][]

![format_png 6][]

![format_png 7][]

![format_png 8][]

![format_png 9][]

![format_png 10][]

![format_png 11][]

————————————

![format_png 12][]

![format_png 13][]

![format_png 14][]

![format_png 15][]

![format_png 16][]

![format_png 17][]

![format_png 18][]

![format_png 19][]

![format_png 20][]

![format_png 21][]

![format_png 22][]

![format_png 23][]

![format_png 24][]

![format_png 25][]

![format_png 26][]

![format_png 27][]

![format_png 28][]

![format_png 29][]

如图中所示，我们把原本的冠军选手5排除掉，在四分之一决赛和他同一组的选手6就自然获得了直接晋级。

接下来的半决赛，选手7打败选手6晋级；在总决赛，选手7打败选手3晋级，成为了新的冠军。

因此我们可以判断出，选手7是总体上的亚军。

![format_png 30][]

![format_png 31][]

![format_png 32][]

![format_png 33][]

![format_png 34][]

![format_png 35][]

![format_png 36][]

假如给定如下数组，要求从小到大进行升序排列：

![format_png 37][]

第一步，我们根据数组建立一颗满二叉树，用于进行“锦标赛式”的多层次比较。数组元素位于二叉树的叶子结点，元素数量不足时，用空结点补齐。

![format_png 38][]

第二步，像锦标赛那样，让相邻结点进行两两比较，把数值较小的结点“晋升“到父结点。

![format_png 39][]

如此一来，树的根结点一定是值最小的结点，把它复制到原数组的最左侧：

![format_png 40][]

第三步，删除原本的最小结点，也就是值为1的结点。然后针对该结点所在路径，进行重新比较和刷新。

如此一来，树的根结点换成了第二小的结点，把它复制到原数组的下一个位置：

![format_png 41][]

第四步，删除原本第二小的结点，也就是值为2的结点。然后针对该结点所在路径，进行重新比较和刷新。

如此一来，树的根结点换成了第三小的结点，把它复制到原数组的下一个位置：

![format_png 42][]

像这样不断删除剩余的最小结点，局部刷新二叉树，最终完成了数组的升序排列：

![format_png 43][]

![format_png 44][]

![format_png 45][]

public class TournamentSort {
    
        public static void tournamentSort(int[] array) {
            Node[] tree = buildTree(array);
    
            for(int i=0; i<array.length; i++){
                array[i] = tree[0].data;
                if(i<array.length-1) {
                    //当前最小元素所对应的叶子结点置空
                    tree[tree[0].index] = null;
                    //重新选举最小元素
                    updateTree(tree[0].index, tree);
                }
            }
        }
    
        //排序前为数组构建二叉树，并选举最小值到树的根结点
        public static Node[] buildTree(int[] array) {
            //计算叶子层的结点数
            int leafSize = nearestPowerOfTwo(array.length);
            //计算二叉树的总结点数
            int treeSize = leafSize * 2 - 1;
            Node[] tree = new Node[treeSize];
            //填充叶子结点
            for(int i=0; i<array.length; i++){
                tree[i+leafSize-1] = new Node(i+leafSize-1, array[i]);
            }
            //自下而上填充非叶子结点
            int levelSize = leafSize;
            int lastIndex = treeSize-1;
            while(levelSize > 1){
                for(int i=0; i<levelSize; i+=2){
                    Node right = tree[lastIndex-i];
                    Node left = tree[lastIndex-i-1];
                    Node parent = left;
                    if(left != null && right != null) {
                        parent = left.data<right.data?left:right;
                    }else if (left == null){
                        parent = right;
                    }
                    if(parent != null){
                        int parentIndex = (lastIndex-i-1)/2;
                        tree[parentIndex] = new Node(parent.index, parent.data);
                    }
                }
                lastIndex -= levelSize;
                levelSize = levelSize/2;
            }
            return tree;
        }
    
        //重新选举最小元素
        public static void updateTree(int index, Node[] tree){
    
            while(index != 0){
                Node node = tree[index];
                Node sibling = null;
                if((index&1) == 1){
                    //index为奇数，该结点是左孩子
                    sibling = tree[index+1];
                }else {
                    //index为偶数，该结点是右孩子
                    sibling = tree[index-1];
                }
    
                Node parent = node;
                int parentIndex = (index-1)/2;
                if(node != null && sibling != null) {
                    parent = node.data<sibling.data?node:sibling;
                }else if (node == null){
                    parent = sibling;
                }
                tree[parentIndex] = parent==null ? null : new Node(parent.index, parent.data);
                index = parentIndex;
            }
        }
    
        //获得仅大于number的完全平方数
        public static int nearestPowerOfTwo(int number) {
            int square = 1;
            while(square < number){
                square = square<<1;
            }
            return square;
        }
    
        //结点类
        private static class Node {
            int data;
            int index;
    
            Node(int index, int data){
                this.index = index;
                this.data = data;
            }
        }
    
        public static void main(String[] args) {
            int[] array = {9,3,7,1,5,2,8,10,11,19,4};
            tournamentSort(array);
            System.out.println(Arrays.toString(array));
        }
    
    }

在这段代码中，二叉树的存储方式并非传统的链式存储，而是采用数组进行存储。因此，该二叉树的每一个父结点下标，都可以由（孩子下标-1）/2 来获得。

![format_png 46][]

![format_png 47][]

![format_png 48][]

![format_png 49][]

![format_png 50][]

![format_png 51][]

—————END—————

喜欢本文的朋友，欢迎关注公众号 **程序员小灰**，收看更多精彩内容

![format_png 52][]

点个[在看]，是对小灰最大的支持！

[format_png]: /images/20221023/bd2e9c293d994749b80a554450b3a579.png
[format_png 1]: /images/20221023/2763f51c46b5479f95e0ed0979fdacb9.png
[format_png 2]: /images/20221023/3adf6a20f18d4bd8b7d940a173894055.png
[format_png 3]: /images/20221023/56f0de94926e46c0adbaed809f487db6.png
[format_png 4]: /images/20221023/6c66f019c2f04d15973178e0145973d8.png
[format_png 5]: /images/20221023/79e30aba1aa04f95a731b619523de198.png
[format_png 6]: /images/20221023/f1dac8c3958d490d9a78415372f1f2b2.png
[format_png 7]: /images/20221023/7b4dd55dd8464d0397cf4449385196e3.png
[format_png 8]: /images/20221023/6b6f48cf76474dffa2e12e279d6917fc.png
[format_png 9]: /images/20221023/0d864cc7035c44e5896988505d039a47.png
[format_png 10]: /images/20221023/88236302e48e4c11bac9b49d41a9e1ff.png
[format_png 11]: /images/20221023/e9b60dd1880d4ed895f52af91812c3ec.png
[format_png 12]: /images/20221023/892675d20bfc4447a14fa431ce5d745f.png
[format_png 13]: /images/20221023/73e8db9a9a1d4cacbdfbb09036dbaab2.png
[format_png 14]: /images/20221023/15e468cd8b7e4af4929f3670b44a0655.png
[format_png 15]: /images/20221023/f350c1dbb1fc4a4eb2079d1810b251db.png
[format_png 16]: /images/20221023/582a30fecde143138170821e280731b7.png
[format_png 17]: /images/20221023/1a4ed918589c4c12b39e687930882795.png
[format_png 18]: /images/20221023/cb043b9caa68478ea13846801a01c69f.png
[format_png 19]: /images/20221023/3cfb8dc78df343aa936b28582fa28aa4.png
[format_png 20]: /images/20221023/7f94b04106ca4d2cbcae2dd07e9aabb6.png
[format_png 21]: /images/20221023/a10609bbb06446f3a86a1b2866c57a5d.png
[format_png 22]: /images/20221023/87b344c727f348a3ae38902a585ff4e3.png
[format_png 23]: /images/20221023/bff9427efba94edeb8cedad977d5a3ac.png
[format_png 24]: /images/20221023/78016da6a79c4b56a60b858f908a69cb.png
[format_png 25]: /images/20221023/2392feb3faf64ecfaf0b7c8e0d57e0d5.png
[format_png 26]: /images/20221023/215ecb99df874dd881951d5f4218b4b1.png
[format_png 27]: /images/20221023/cc9e0fbed446421f95cdaceb1f861319.png
[format_png 28]: /images/20221023/68cdd687c4cc4fc98fe57d4fa97d5a03.png
[format_png 29]: /images/20221023/1de349b0a14c4a5db268a42fdb09b650.png
[format_png 30]: /images/20221023/c48ef41de1ef487a9418fae91302a964.png
[format_png 31]: /images/20221023/8ad5f2e17ac14b35a8564fb88b8a36ed.png
[format_png 32]: /images/20221023/5d4b4f41b7a94a36b62eef8a909a64b0.png
[format_png 33]: /images/20221023/db40643e4fbb491e82a2dc06f7b1e6b9.png
[format_png 34]: /images/20221023/3e674cf2677d42d0be232f2856bbb395.png
[format_png 35]: /images/20221023/76d76a68044149f885c10932c023a635.png
[format_png 36]: /images/20221023/c3a8758c38614606ba49d14fb857ab2c.png
[format_png 37]: /images/20221023/64966c537e6d41de96e10ef7b4a025fb.png
[format_png 38]: /images/20221023/c2f7f1f9b94c48459efd0da3f18eddb5.png
[format_png 39]: /images/20221023/3c52a331073b49728bf3fd6a8062a29d.png
[format_png 40]: /images/20221023/b6ea32c3525e412197b979106fb3ad61.png
[format_png 41]: /images/20221023/aa8de1b70e084aad88d8197daf447573.png
[format_png 42]: /images/20221023/607eb662046c4bf1bdb2dbd513ef6d83.png
[format_png 43]: /images/20221023/701e05246fcb4a688da1397793ccfbbe.png
[format_png 44]: /images/20221023/8e307e1138694fd79ce7ea8b40f824f3.png
[format_png 45]: /images/20221023/e8be22e74251485c8f7c40542a5a7865.png
[format_png 46]: /images/20221023/9f9c852075a247579d391174291d297e.png
[format_png 47]: /images/20221023/8166070cc973460a8c99a81ea3e24f7f.png
[format_png 48]: /images/20221023/f939887fa2634c8c99c53c887a1a35b5.png
[format_png 49]: /images/20221023/f72f1e75693d4530a482f5c6e12cb6c6.png
[format_png 50]: /images/20221023/5d24d485e6b74dfb899038bb83d56b1a.png
[format_png 51]: /images/20221023/fa30673e3e1c41c69b76c69631723943.png
[format_png 52]: /images/20221023/8cfad496f3544823a568ff93cf2e9c84.png