漫畫：什么是 “錦標(biāo)賽排序” ？

時(shí)間：2021-03-11 10:04:36

關(guān)鍵字：錦標(biāo)賽排序選擇排序算法

手機(jī)看文章

掃描二維碼
隨時(shí)隨地手機(jī)看文章

[導(dǎo)讀]你了解選擇排序嗎？

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

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

如圖中所示，我們把原本的冠軍選手5排除掉，在四分之一決賽和他同一組的選手6就自然獲得了直接晉級。

接下來的半決賽，選手7打敗選手6晉級；在總決賽，選手7打敗選手3晉級，成為了新的冠軍。

因此我們可以判斷出，選手7是總體上的亞軍。

假如給定如下數(shù)組，要求從小到大進(jìn)行升序排列：

第一步，我們根據(jù)數(shù)組建立一顆滿二叉樹，用于進(jìn)行“錦標(biāo)賽式”的多層次比較。數(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)。

如此一來，樹的根結(jié)點(diǎn)一定是值最小的結(jié)點(diǎn)，把它復(fù)制到原數(shù)組的最左側(cè)：

第三步，刪除原本的最小結(jié)點(diǎn)，也就是值為1的結(jié)點(diǎn)。然后針對該結(jié)點(diǎn)所在路徑，進(jìn)行重新比較和刷新。

如此一來，樹的根結(jié)點(diǎn)換成了第二小的結(jié)點(diǎn)，把它復(fù)制到原數(shù)組的下一個(gè)位置：

第四步，刪除原本第二小的結(jié)點(diǎn)，也就是值為2的結(jié)點(diǎn)。然后針對該結(jié)點(diǎn)所在路徑，進(jìn)行重新比較和刷新。

如此一來，樹的根結(jié)點(diǎn)換成了第三小的結(jié)點(diǎn)，把它復(fù)制到原數(shù)組的下一個(gè)位置：

像這樣不斷刪除剩余的最小結(jié)點(diǎn)，局部刷新二叉樹，最終完成了數(shù)組的升序排列：

public class TournamentSort { public static void tournamentSort(int[] array) {
        Node[] tree = buildTree(array); for(int i=0; i0].data; if(i1) { //當(dāng)前最小元素所對應(yīng)的葉子結(jié)點(diǎn)置空 tree[tree[0].index] = null; //重新選舉最小元素 updateTree(tree[0].index, tree);
            }
        }
    } //排序前為數(shù)組構(gòu)建二叉樹，并選舉最小值到樹的根結(jié)點(diǎn) public static Node[] buildTree(int[] array) { //計(jì)算葉子層的結(jié)點(diǎn)數(shù) int leafSize = nearestPowerOfTwo(array.length); //計(jì)算二叉樹的總結(jié)點(diǎn)數(shù) int treeSize = leafSize * 2 - 1;
        Node[] tree = new Node[treeSize]; //填充葉子結(jié)點(diǎn) for(int i=0; i1] = new Node(i+leafSize-1, array[i]);
        } //自下而上填充非葉子結(jié)點(diǎn) int levelSize = leafSize; int lastIndex = treeSize-1; while(levelSize > 1){ for(int i=0; i2){
                Node right = tree[lastIndex-i];
                Node left = tree[lastIndex-i-1];
                Node parent = left; if(left != null && right != null) {
                    parent = left.dataelse 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.dataelse 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)類 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));
    }

}