一个特别有意思的算法——锦标赛算法

我们应该多去研究我们学的专业，并在前辈所总结的知识道理上挖掘出更深的知识。
超越前辈是一种社会主潮流。如果我们这一代比起前辈没有进步，那社会怎么发展。

本篇介绍一个特别有趣的算法——锦标赛算法，运用锦标赛算法可以更好的去找最大和第二大的数。

1、蛮力法找最大和第二大

我们在上一篇已经知道找最大和最小的算法，用蛮力法找最大和最小的T(n)是2n-3。同样的，用蛮力法找最大和第二大也是T(n)=2n-3。

我们来直接看代码

public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[]=new int[11];
		Random random=new Random();
		for(int i=0;i<a.length;i++)
			a[i]=random.nextInt(101);  //随机生成10个0到100的数字
		System.out.println("生成的结果是："+Arrays.toString(a));
		int secondmaxi = FindsecondMax2(a);
		System.out.println("第二大的数是："+secondmaxi);
	}

//蛮力法2
    public static int FindsecondMax2(int a[]) {
    	int max=-0x3f3f3f3f;
    	int secondmax=-0x3f3f3f3f;
    	
    	for(int i=0;i<a.length;i++)
    		if(max<a[i])
    		{
    			secondmax=max;
    			max=a[i];
    		}
    		else if(secondmax<a[i]&&a[i]!=max) //将和max一样的数据忽略掉，找到第二大的数
    			secondmax=a[i];
    	return secondmax;
    }

2、锦标赛算法

什么是锦标赛算法？

在进行锦标赛的时候，首先将参赛队员抽签进行两两分组，将抽到相同号的参赛队员分为一组

然后进行第一轮比赛，第一轮比赛结果如下

将比分低的进行淘汰，随后我们将晋级的参赛队员进行两两分组，这里会有一个人没法分组，那么在第二轮直接轮空。

然后进行第二轮比赛，结果如下

将最后两个人进行最后一轮比赛，结果如下

最后看到，庚赢得最后胜利成为了第一名，而丁得了第二名。

我们抽出这一模型来进行找最大和第二大
1、首先进行两两分组比较，大的数进入下一轮；被淘汰的数标记在淘汰它的元素的上方
2、每轮进行比拼，直到剩下1个元素即max为止
3、然后在max被淘汰的数里面找到最大的数，这个最大的数就是数组里的第二大的数

我们来看个例子：





我们看到100是最大的那个数，然后我们把被100淘汰的数7，95，52里面找一个最大的数95，这个数就是数组中第二大的数。

我们抽出来进行代码分析：
首先我们开辟一个是原数组2倍长度的临时数组

先将原数组中的元素放到临时数组的后面
i=2·n-1,i>=n,i- -

随后我们进行竞技，从后往前两两分组比较，将较大的数填在n之前的位置。一直到n=1为止
i=2·n-2,i>=2,i-=2 第一轮：
第二轮：
第三轮：

随后我们找到了最大的数100。

然后我们进入第二阶段：找第二大

大家看下上面的示意图，不难发现：
i=1,i<n
如果第i个和第2·i个元素相等时,那么第二大的值可能出现在第2·i+1的位置上
然后i=2·i

如果第i个和第2·i+1个元素相等时，那么第二大的值可能出现在第2·i的位置上
然后i=2·i+1

然后我们以此编写代码

public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[]=new int[11];
		Random random=new Random();
		for(int i=0;i<a.length;i++)
			a[i]=random.nextInt(101);  //随机生成10个0到100的数字
		System.out.println("生成的结果是："+Arrays.toString(a));
		int secondmaxi = FindsecondMax2(a);
		System.out.println("第二大的数是："+secondmaxi);
	}

//锦标赛算法
    public static int ChampionShip(int a[]) {
    	int temp[]=new int[2*a.length];
    	int secondmax=-0x3f3f3f3f;
    	
    	//将数组里面的数据填在临时数组中的temp[a.length-1]的后面
    	for(int i=temp.length-1;i>=a.length;i--) 
    		temp[i]=a[i-a.length];
    	
    	//从后往前进行比较，将最大值以此填在temp[1]到temp[a.length-1]之间，则temp[1]是数组中的最大值
    	for(int i=temp.length-2;i>=2;i-=2)
    		temp[i/2]=Math.max(temp[i], temp[i+1]);
    	
    	//我们将从直接输给最大值的数中找到第二大的数
    	for(int i=1;i<a.length;) {
    		if(temp[i]==temp[2*i]) {
    			if(secondmax<temp[2*i+1])
    				secondmax=temp[2*i+1];
    			i=i*2;
    		}
    		
    		
    		else {
    			if(secondmax<temp[2*i])
    				secondmax=temp[2*i];
    			i=2*i+1;
    		}
    	}
    	return secondmax;
    }

这个代码是没有考虑当max出现多个时，第二大应该在删去重复的max之后剩下的元素中找。因为第二大是被max打败的，然而max有多个不知道是被谁打败的。当然，这里征求一个好的想法和代码

下面我们对锦标赛算法进行分析：

分析这个算法，主要是分析比较次数

好，我们能看到在选第二大的算法中，锦标赛算法是一个最好的算法

以上就是锦标赛算法的内容

######                 是以前辈汲汲求知也（沈继祖《和阎帅侍郎见寄 》）