百度面試題 --- 錦標賽排序

面了一次百度，暫時完成兩輪技術面試，感覺每次都好多題目，並且有一些不知道怎麼回答，看來准備的還是不夠好。

先分享一個題目吧：

給出一個長度是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. }