学步园

今天在做游戏的联赛系统，假如有N 人报名参加联赛，服务器记录下报名人数，并对这些人的战斗后的结果进行排序，决出前16强或者8强。

网上找了下锦标赛排序算法，内容真少。总结下：

1：建树：这里说的建树是建立一颗完全二叉树。当参加排序的数组不足2的N次幂，将其补足。直到满足建立一个完全二叉树

2：当某结点的比较对手的参选标志为“不再参选”，该结点自动升入双亲结点，此动作不计入排序码比较次数。每次比较出来的第一名都标记为不参赛。

3：最终结果是返回到原来的数组之中

4：堆排序，资料很多，不多说。

/**
 * 联赛系统分组
 * 
 * @author Administrator
 */
public class Competition {

	/**
	 * Player改为玩家ID存储
	 */
	private Player[] playerArray;
	
	public Competition() {
		int playerNum = World.getIns().getCompetition().size();
		Player[] playerArray = (Player[]) World.getIns().getCompetition()
				.toArray();
		TournamentSort(playerArray,playerNum);
		
		//比赛后结果排序按照数组顺序，放入playerArray中
	}

	/**
	 * 创建一颗树
	 * @param a
	 * @param n
	 */
	public static void TournamentSort(Player[] player, int n) {
		TournamentPlayer[] tree;

		int bottomRowSize = nearestPowerOfTwo(n);// 计算满足>=n的2的最小次幂的数:
		int TreeSize = 2 * bottomRowSize - 1;
		int loadindex = bottomRowSize - 1; // 外结点开始位置：从根节点开始往下数

		tree = new TournamentPlayer[TreeSize];
		for (int i = 0; i < TreeSize; i++) {
			tree[i] = new TournamentPlayer();
		}

		int j = 0; // 在数组player中取数据指针

		for (int i = loadindex; i < TreeSize; i++) { // 复制数组数据到树的外结点中
			tree[i].setIndex(i); // 下标
			if (j < n) {
				tree[i].setActive(1);
				tree[i].setData(player[j++]);
			} // 复制数据
			else {
				tree[i].setActive(0); // 后面的结点为空的外结点
			}

			// System.out.println(tree[i].getIndex()+" "+ tree[i].getData());
		}

		int i = loadindex; // 进行初始比较寻找最小的项

		while (i != 0) {
			j = i;
			while (j < 2 * i) { // 处理各对比赛者
				Player playerRight = tree[j].getData();
				Player playerLeft = tree[j + 1].getData();
				// @ TODO 计算战斗，返回左边赢
				boolean isLeftWin = true;

				if (tree[j + 1].getActive() == 0 || isLeftWin == true)
					tree[(j - 1) / 2] = tree[j]; // 胜者送入双亲
				else
					tree[(j - 1) / 2] = tree[j + 1];
				// System.out.println(tree[(j - 1) / 2].getIndex()+" "+ tree[(j
				// - 1) / 2].getData());

				j += 2; // 下一对参加比较的项
			}
			i = (i - 1) / 2; // i退到双亲, 直到i=0为止
			// System.out.println(tree[(j - 1) / 2].getIndex() + " "
			// + tree[(j - 1) / 2].getData());
		}

		for (i = 0; i < n - 1; i++) { // 处理其它n-1元素
			player[i] = tree[0].getData(); // 当前最小元素送数组a
			System.out.println(player[i]);

			tree[tree[0].getIndex()].setActive(0); // 该元素相应外结点不再比赛

			UpdateTree(tree, tree[0].getIndex()); // 从该处向上修改

		}
		player[n - 1] = tree[0].getData();

		System.out.println(player[n - 1]);
		// return tree;

	}

	/**
	 * 每次比较出胜者之后，更新得到下一次比较的胜者
	 * i是表中当前最小元素的下标, 即胜者。从它开始向上调整。
	 * @param tree
	 * @param i
	 */
	public static void UpdateTree(TournamentPlayer[] tree, int i) {
		if (i % 2 == 0)
			tree[(i - 1) / 2] = tree[i - 1]; // i为偶数, 对手为左结点
		else
			tree[(i - 1) / 2] = tree[i + 1]; // i为奇数, 对手为右结点
		// 最小元素输出之后, 它的对手上升到父结点位置
		i = (i - 1) / 2;
		int j = 0;// i上升到双亲结点位置
		while (i != 0) {
			if (i % 2 == 0)
				j = i - 1; // 确定i的对手是左结点还是右结点
			else
				j = i + 1;
			if (tree[i].getActive() == 0 || tree[j].getActive() == 0) {// 比赛对手中间有一个为空
				if (tree[i].getActive() != 0)
					tree[(i - 1) / 2] = tree[i];
				else
					tree[(i - 1) / 2] = tree[j];
			}// 非空者上升到双亲结点
			else // 比赛对手都不为空
			{
				Player playerRight = tree[i].getData();
				Player playerLeft = tree[j].getData();
				// @ TODO 计算战斗，返回左边赢
				boolean isLeftWin = true;

				if (isLeftWin)
					tree[(i - 1) / 2] = tree[i];
				else
					tree[(i - 1) / 2] = tree[j]; // 胜者上升到双亲结点
				i = (i - 1) / 2; // i上升到双亲结点
			}
		}

	}

	/**
	 * 得到最接近且大于
	 * number的2的N的方
	 * @param number
	 * @return
	 */
	public static int nearestPowerOfTwo(int number) {
		--number;
		number |= number >> 16;
		number |= number >> 8;
		number |= number >> 4;
		number |= number >> 2;
		number |= number >> 1;
		++number;
		return number;
	}

	public static void main(String[] args) {
		Player[] relust =  new Competition().getPlayerArray();
	}

	public Player[] getPlayerArray() {
		return playerArray;
	}

	public void setPlayerArray(Player[] playerArray) {
		this.playerArray = playerArray;
	}

}