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

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

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

```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));
}

}
```

—————END—————

0 条评论

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

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

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

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

• ### 漫画：插入排序是什么？

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

• ### 漫画：什么是归并排序？

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

• ### 漫画：什么是选择排序？

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

• ### 漫画：什么是插入排序？

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

• ### 漫画：什么是希尔排序？

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

• ### 漫画：插入排序是什么？

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

• ### 漫画：什么是计数排序？

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

• ### 漫画：什么是计数排序？

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

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

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

• ### 漫画：什么是计数排序？

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

• ### 漫画：什么是插入排序？

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

• ### 【漫画】什么是外部排序？【转】

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

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

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

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

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

• ### 动画 | 什么是桶排序？

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

• ### 动画 | 什么是堆排序？

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