锦标赛排序

[Xeonacid]

https://oi-wiki.org/basic/tournament-sort/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[szp14]

recreat函数中

if (i % 2 == 0 && i < 2 * n - 1)
      j = i + 1;
else
      j = i - 1;

换成

      j = i ^ 1;

会不会好一点？

[qwq2519]

不好，可读性下降

[zhangjialin996]

手动模拟一遍基本知道代码怎么回事了，值得一提的是，这颗竞标赛树一定是完全二叉树，而树中有节点数量结论：n0 = n2 + 1，所以tmp的tmp[0]是用不上的

import java.util.*;

public class LeetcodeTest {
  public int[] sortArray(int[] nums){
    tournamentSort(nums);
    return nums;
}

// 竞标赛排序
public void tournamentSort(int[] nums){
    int[] tmp = new int[nums.length * 2];
    for(int i = 0; i < nums.length; i++){
        tmp[i + nums.length] = nums[i];
    }

    // 初始化竞标赛树（类似败者树）
    for(int i = 2 * nums.length - 1; i > 0; i-=2) {
        int k = i / 2;
        int j = i - 1;
        tmp[k] = getWinner(tmp, i , j);
    }

    // 取出冠军后，需要重新选择新的冠军
    for(int i = 0; i <= nums.length - 1; i++){
        int champership = tmp[tmp[1]];
        tmp[tmp[1]] = Integer.MAX_VALUE;
        nums[i] = champership;
        if(i == nums.length - 1) break;
        // 调整竞标赛树
        int champershipIndex = tmp[1];
        while(champershipIndex > 1){
            int k = champershipIndex / 2;
            int j;
            if(champershipIndex % 2 == 0 && champershipIndex < 2 * nums.length - 1) j = champershipIndex + 1;
            else j = champershipIndex - 1;
            tmp[k] = getWinner(tmp, champershipIndex, j);
            champershipIndex = k;
        }
    }
}

// 返回胜者在[n, 2n - 1]之间的索引
public int getWinner(int[] tmp, int i, int j){
    int iIndex = i >= (tmp.length / 2) ? i : tmp[i];
    int jIndex = j >= (tmp.length / 2) ? j : tmp[j];
    if(tmp[iIndex] <= tmp[jIndex]) return iIndex;
    return jIndex;
}

  public static void main(String... args){
    int[] arr = {5,2,3,1,6,8,9,1};
    // int[] arr = {3, -1};
    LeetcodeTest t = new LeetcodeTest();
    // PriorityQueue
    t.tournamentSort(arr);
    System.out.println(Arrays.toString(arr));
  }
}

[xiaolefrank]

感觉这个算法的python版本可能存在点小问题?

我在本地debug的时候观测了感觉是索引值跳转的问题

首先tmp这个数组index范围[n,2n)处存放的是a数组的数值.

根据算法的核心思想,是对要排序的元素进行树的构建(设这棵树的深度为k).程序对于树的处理是把这棵树的1~k-1层部分存放两两元素比较的产生的结果的索引值,也即是tmp的index[0,n)部分.这里的树的k层顺序存放a的各个元素.

然而当这棵树的深度k大于3之后,仅用一次跳转只能到构建排序树中这个节点的下一层子节点,页面中提供的示例程序只能对一次跳转后的值进行比较, 但是这个值并不一定是a中的数值,而可能是索引值, 利用函数winner的比较没有意义.

还有一个小问题:python中的inf(infinity)是float类型的,如果利用str类型的'INF'进行标识的话应该在winner函数里对无穷的情况专门判断.

下面是个人改进的参考程序:

#example
from random import sample
arr=sample(range(1,10),6)
n=6
tmp=[0]*12

def go_to_value_num(num):
    while num<n:
        num=tmp[num]
    return num

def winner(i,j):
    u=go_to_value_num(i)
    v=go_to_value_num(j)
    if tmp[u]=='INF': return v
    if tmp[v]=='INF': return u
    if tmp[u]<=tmp[v]:
        return i
    return j

def create_tree():
    for i in range(n):
        tmp[n+i]=arr[i]
    for i in range(2*n-1,1,-2):
        k=int(i/2)
        j=i-1
        tmp[k]=winner(i,j)
    value=tmp[go_to_value_num(1)]
    tmp[go_to_value_num(1)]='INF'
    return value
def recreate():
    i=go_to_value_num(1)
    while i>1:
        j=k=int(i/2)
        if i%2==0:
            j=i+1
        else:
            j=i-1
        tmp[k]=winner(i,j)
        i=k
    value=tmp[go_to_value_num(1)]
    tmp[go_to_value_num(1)]='INF'
    return value
def tournament_sort():
    val=create_tree()
    for i in range(n):
        arr[i]=val
        val=recreate()

print(arr)
tournament_sort()
print(arr)

其实就是多加一个小函数,但是可能时间复杂度会增加.