专栏首页程序员小灰漫画:什么是 “锦标赛排序” ?

漫画:什么是 “锦标赛排序” ?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 来获得。

—————END—————

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

本文分享自微信公众号 - 程序员小灰(chengxuyuanxiaohui),作者:小灰

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-03-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【漫画】什么是外部排序?

    排序的时候我们可以选择快速排序或归并排序等算法。为了方便,我们把排序好的2G有序数据称之为有序子串吧。接着我们可以把两个小的有序子串合并成一个大的有序子串。

    帅地
  • 【漫画】什么是外部排序?

    排序的时候我们可以选择快速排序或归并排序等算法。为了方便,我们把排序好的2G有序数据称之为有序子串吧。接着我们可以把两个小的有序子串合并成一个大的有序子串。

    小小詹同学
  • 漫画:插入排序是什么?

    其实从图中你可以感受到插入排序是一个比较简单的排序,没有过多的复杂步骤。它排序的基本原理也非常的简单,对于没有排序的元素,在已排序的元素中从后往前依次扫描,找到...

    Python进击者
  • 漫画:什么是归并排序?

    归并排序和擂台赛有一个很大的不同,就是擂台赛只需要决定谁是老大,而并不关心谁做老二和老三;归并排序的要求复杂一些,需要确定每一个元素的排列位置。

    小灰
  • 漫画:什么是选择排序?

    顾名思义,就是把每一元素和下一个元素进行比较和交换,使得较大的元素像气泡一样向右侧移动:

    小灰
  • 漫画:什么是插入排序?

    这时候,我又抓到了一张红桃8,如何让手中的五张牌重新变成升序呢?用冒泡排序,选择排序,亦或是快速排序?

    小灰
  • 漫画:什么是希尔排序?

    插入排序顾名思义,就是在排序的过程中,把数组的每一个元素按照大小关系,插入到前面有序区的对应位置。

    小灰
  • 漫画:插入排序是什么?

    其实从图中你可以感受到插入排序是一个比较简单的排序,没有过多的复杂步骤。它排序的基本原理也非常的简单,对于没有排序的元素,在已排序的元素中从后往前依次扫描,找到...

    lucifer210
  • 漫画:什么是计数排序?

    计数排序(Counting Sort)是一种针对于特定范围之间的整数进行排序的算法。它通过统计给定数组中不同元素的数量(类似于哈希映射),然后对映射后的数组进行...

    五分钟学算法
  • 漫画:什么是计数排序?

    计数排序(Counting Sort)是一种针对于特定范围之间的整数进行排序的算法。它通过统计给定数组中不同元素的数量(类似于哈希映射),然后对映射后的数组进行...

    灵魂画师牧码
  • 【漫画】什么是外部排序?

    排序的时候我们可以选择快速排序或归并排序等算法。为了方便,我们把排序好的2G有序数据称之为有序子串吧。接着我们可以把两个小的有序子串合并成一个大的有序子串。

    Java3y
  • 漫画:什么是计数排序?

    9,3,5,4,9,1,2,7,8,1,3,6,5,3,4,0,10,9 ,7,9

    程序员小明
  • 漫画:什么是插入排序?

    这时候,我又抓到了一张红桃8,如何让手中的五张牌重新变成升序呢?用冒泡排序,选择排序,亦或是快速排序?

    macrozheng
  • 【漫画】什么是外部排序?【转】

    还记得面试现场第一篇文章【面试现场】如何判断一个数是否在40亿个整数中?发出之后,最后蛋哥说把40亿个数先进行外部排序。有读者问到,内存无法一次性加载40亿个数...

    233333
  • Python可以被用来做哪些神奇好玩的事情

    关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 如果你在周末、有WIFI的房间里不知...

    昱良
  • Python可以被用来做哪些神奇好玩的事情

    如果你在周末、有WIFI的房间里不知道做什么,不如学下Python吧。有了它,你可以什么都不需要! 基础需求篇:温饱与空虚 躺着赚钱 一位匿名知乎网友爆料...

    小小科
  • 动画 | 什么是桶排序?

    学过上一篇文章的计数排序之后,特别是归约化分治处理的计数排序(适用于较离散的非负整数序列)。计数排序的局限比较多,在排序之前需要解决负数和小数的问题,而桶排序不...

    我脱下短袖
  • 动画 | 什么是堆排序?

    回顾一下我们学过的 选择排序 ,在无序区找到一个最小(大)的元素需要比较n-1次,找到第二小的元素需要比较n-2次,直到最后比较1次。而堆排序因为二叉堆的性质,...

    我脱下短袖
  • 一代宗师之多福八段锦 - 腾讯ISUX

    腾讯ISUX

扫码关注云+社区

领取腾讯云代金券