百度面试题 — 锦标赛排序

面了一次百度，暂时完成两轮技术面试，感觉每次都好多题目，并且有一些不知道怎么回答，看来准备的还是不够好。

先分享一个题目吧：

给出一个长度是N的数组，现在要找出最大的两个元素，最少要多少次比较。

分析： 如果找出1个最大的，比较次数无疑是 n – 1,

现在如果已经找出最大的了，那么再找第二大的，如果用竞赛排序的方法，可以再使用 logn就可以找到了。 不过不知道怎么证明 这是最小次数。

顺便实现了一下 竞赛排序。

1. public class TournamentSort { 
2.  
3.  
4.     private class Node//用node来存储竞赛排序过程中的节点，包括里面的数据和数据在数组中的ID  
5.     { 
6.         public int data; 
7.         public int id; 
8.          
9.         public Node() 
10.         { 
11.              
12.         } 
13.         public Node(int _data, int _id)//  
14.         { 
15.             data = _data; 
16.             id = _id; 
17.         } 
18.     } 
19.     public void Adjust(Node[] data, int idx)//当去除最小元素以后，我们要调整数组  
20.     { 
21.         while(idx != 0) 
22.         { 
23.             if(idx % 2 == 1)//当前id是奇数，说明并列的是idx + 1, 父节点是 (idx-1)/2  
24.             { 
25.                 if(data[idx].data < data[idx + 1].data) 
26.                 { 
27.                     data[(idx – 1)/2] = data[idx]; 
28.                 } 
29.                 else 
30.                 { 
31.                     data[(idx-1)/2] = data[idx + 1]; 
32.                 } 
33.                 idx = (idx – 1)/2; 
34.             } 
35.             else 
36.             { 
37.                 if(data[idx-1].data < data[idx].data) 
38.                 { 
39.                     data[idx/2 – 1] = data[idx-1]; 
40.                 } 
41.                 else 
42.                 { 
43.                     data[idx/2 – 1] = data[idx]; 
44.                 } 
45.                 idx = (idx/2 – 1); 
46.             } 
47.         } 
48.     } 
49.      
50.      
51.     public void Sort(int[] data) 
52.     { 
53.         int nNodes = 1; 
54.         int nTreeSize; 
55.         while(nNodes < data.length) 
56.         { 
57.             nNodes *= 2; 
58.         } 
59.         nTreeSize = 2 * nNodes – 1;//竞赛树节点的个数, nNode算出来是为了做成满二叉树  
60.          
61.         Node[] nodes = new Node[nTreeSize];//竞赛树用数组存储  
62.         //initialize the data  
63.          
64.         int i, j; 
65.         int idx; 
66.         for( i = nNodes – 1; i < nTreeSize; i++) //初始化竞赛树数据  
67.         { 
68.             idx = i – (nNodes – 1); 
69.             if(idx < data.length) 
70.             { 
71.                 nodes[i] = new Node(data[idx], i); 
72.             } 
73.             else 
74.             { 
75.                 nodes[i] = new Node(Integer.MAX_VALUE, –1);//对于补充的数据，我们初始化成最大。  
76.             } 
77.              
78.         } 
79.          
80.         for( i = nNodes – 2; i >= 0; i–)//  
81.         { 
82.             nodes[i] = new Node(); 
83.             if(nodes[i * 2 + 1].data < nodes[i * 2 + 2].data) 
84.             { 
85.                 nodes[i] = nodes[i*2 + 1]; 
86.             } 
87.             else 
88.             { 
89.                 nodes[i] = nodes[i*2 + 2]; 
90.             } 
91.         } 
92.         //the real sorting procedure  
93.         for( i = 0; i < data.length; i++)//实际排序的过程  
94.         { 
95.             data[i] = nodes[0].data;//取出最小的  
96.             nodes[nodes[0].id].data = Integer.MAX_VALUE; 
97.             Adjust(nodes, nodes[0].id); 
98.              
99.         } 
100.          
101.          
102.          
103.     } 
104. }