漫畫(huà)：什么是 “錦標(biāo)賽排序” ？
————— 第二天 —————
————————————
如圖中所示，我們把原本的冠軍選手5排除掉，在四分之一決賽和他同一組的選手6就自然獲得了直接晉級(jí)。
接下來(lái)的半決賽，選手7打敗選手6晉級(jí)；在總決賽，選手7打敗選手3晉級(jí)，成為了新的冠軍。
因此我們可以判斷出，選手7是總體上的亞軍。
假如給定如下數(shù)組，要求從小到大進(jìn)行升序排列：
第一步，我們根據(jù)數(shù)組建立一顆滿(mǎn)二叉樹(shù)，用于進(jìn)行“錦標(biāo)賽式”的多層次比較。數(shù)組元素位于二叉樹(shù)的葉子結(jié)點(diǎn)，元素?cái)?shù)量不足時(shí)，用空結(jié)點(diǎn)補(bǔ)齊。
第二步，像錦標(biāo)賽那樣，讓相鄰結(jié)點(diǎn)進(jìn)行兩兩比較，把數(shù)值較小的結(jié)點(diǎn)“晉升“到父結(jié)點(diǎn)。
如此一來(lái)，樹(shù)的根結(jié)點(diǎn)一定是值最小的結(jié)點(diǎn)，把它復(fù)制到原數(shù)組的最左側(cè)：
第三步，刪除原本的最小結(jié)點(diǎn)，也就是值為1的結(jié)點(diǎn)。然后針對(duì)該結(jié)點(diǎn)所在路徑，進(jìn)行重新比較和刷新。
如此一來(lái)，樹(shù)的根結(jié)點(diǎn)換成了第二小的結(jié)點(diǎn)，把它復(fù)制到原數(shù)組的下一個(gè)位置：
第四步，刪除原本第二小的結(jié)點(diǎn)，也就是值為2的結(jié)點(diǎn)。然后針對(duì)該結(jié)點(diǎn)所在路徑，進(jìn)行重新比較和刷新。
如此一來(lái)，樹(shù)的根結(jié)點(diǎn)換成了第三小的結(jié)點(diǎn)，把它復(fù)制到原數(shù)組的下一個(gè)位置：
像這樣不斷刪除剩余的最小結(jié)點(diǎn)，局部刷新二叉樹(shù)，最終完成了數(shù)組的升序排列：
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) {
//當(dāng)前最小元素所對(duì)應(yīng)的葉子結(jié)點(diǎn)置空
tree[tree[0].index] = null;
//重新選舉最小元素
updateTree(tree[0].index, tree);
}
}
}
//排序前為數(shù)組構(gòu)建二叉樹(shù)，并選舉最小值到樹(shù)的根結(jié)點(diǎn)
public static Node[] buildTree(int[] array) {
//計(jì)算葉子層的結(jié)點(diǎn)數(shù)
int leafSize = nearestPowerOfTwo(array.length);
//計(jì)算二叉樹(shù)的總結(jié)點(diǎn)數(shù)
int treeSize = leafSize * 2 - 1;
Node[] tree = new Node[treeSize];
//填充葉子結(jié)點(diǎn)
for(int i=0; i<array.length; i++){
tree[i+leafSize-1] = new Node(i+leafSize-1, array[i]);
}
//自下而上填充非葉子結(jié)點(diǎn)
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為奇數(shù)，該結(jié)點(diǎn)是左孩子
sibling = tree[index+1];
}else {
//index為偶數(shù)，該結(jié)點(diǎn)是右孩子
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的完全平方數(shù)
public static int nearestPowerOfTwo(int number) {
int square = 1;
while(square < number){
square = square<<1;
}
return square;
}
//結(jié)點(diǎn)類(lèi)
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));
}
}
在這段代碼中，二叉樹(shù)的存儲(chǔ)方式并非傳統(tǒng)的鏈?zhǔn)酱鎯?chǔ)，而是采用數(shù)組進(jìn)行存儲(chǔ)。因此，該二叉樹(shù)的每一個(gè)父結(jié)點(diǎn)下標(biāo)，都可以由（孩子下標(biāo)-1）/2 來(lái)獲得。
—————END—————
愛(ài)心三連擊
1.看到這里了就點(diǎn)個(gè)在看支持下吧，你的在看是我創(chuàng)作的動(dòng)力。
2.關(guān)注公眾號(hào)腦洞前端，獲取更多前端硬核文章！加個(gè)星標(biāo)，不錯(cuò)過(guò)每一條成長(zhǎng)的機(jī)會(huì)。
3.如果你覺(jué)得本文的內(nèi)容對(duì)你有幫助，就幫我轉(zhuǎn)發(fā)一下吧。