1     算法描述

组委会正在为美团点评CodeM大赛的决赛设计新赛制。

比赛有 n 个人参加（其中 n 为2的次方），每个参赛者根据资格赛和预赛、复赛的成绩，会有不同的积分。比赛采取锦标赛赛制，分轮次进行，设某一轮有 m 个人参加，那么参赛者会被分为m/2 组，每组恰好 2 人，m/2 组的人分别比赛。我们假定积分高的人肯定获胜，若积分一样，则随机产生获胜者。获胜者获得参加下一轮的资格，输的人被淘汰。重复这个过程，直至决出冠军。现在请问，参赛者A最多可以晋级到第几轮（初始为第0轮）

2     算法分析

本章节的算法分析包括两个步骤：用例分析与逻辑分析。

2.1   用例分析

2.2   逻辑分析

3     算法目标

算法运行的目标是最小化系统资源开销（包括处理器资源开销与内存资源开销）以及最小耗时（算法运行时长）。

4     算法设计

4.1   数据结构设计

4.2   算法逻辑设计

4.2.1 genData输入数据

1.   输入参赛者的积分列表，按照以上的数据结构标准化处理输入

2.   积分排序sortRankFunc算法函数

4.2.2 mainFunc函数主流程设计

1.    对输入的参赛者按照积分高低进行排序

2.   对输入的参赛者按照积分相同的进行分组

3.   对输入的参赛者按照积分的高低次序进行两两分组

4.   比赛

5.   胜利者积分+1，更新胜利者积分

6.   移动胜利者到指定的积分队列

7.   淘汰失败者，设置失败者的状态

8.   产生新的比赛轮次的参赛者，参赛者A胜利则继续执行1步骤，参赛者A失败则结束比赛执行9步骤

9.   输出参赛者A的轮次

4.2.3 sortRankFunc积分排序算法

该算法使用Java Lambda表达式并行流式计算与Map-Reduce分片排序，其流程如下所示：

1.   确定积分分片的大小

2.   对积分分片

3.   并行计算每片积分列表的排序

4.   汇总合并每片排序的积分列表

5     算法实现

5.1   程序语言

本程序分别使用Java语言。

5.2   程序示例

5.2.1 genData函数

5.2.2 getRandomData函数

5.2.3 mainFunc函数

5.2.4 sortRankFunc函数

5.2.5 mergeSort函数

5.2.6 sortPiece函数

5.2.7 insertSort函数

5.2.8 seperatePieces函数

5.2.9 normalCompute函数

5.2.10          saveRecourceCompute函数

5.2.11          testSort函数

5.2.12          testPiecesSort函数

6     算法验证

本算法验证测试使用代码覆盖率测试方法。

6.1   测试用例

6.2   执行用例

测试用例通过率100%，代码覆盖率100%。

7     算法效率

7.1   时间复杂度

由代码可知该算法的时间复杂度等于O(N的多次方)。

7.2   空间复杂度

该算法使用一维数组，其空间复杂度是常数。

7.3   性能测试

由以上的性能测试可知，每增加一个数量级范围，耗时线性增长。

7.4   算法优化

已启动多线程并行的处理。

（未完待续）