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

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

先分享一個題目吧：

給出一個長度是N的數組，現在要找出最大的兩個元素，最少要多少次比較。

分析： 如果找出1個最大的，比較次數無疑是 n - 1,

現在如果已經找出最大的了，那麼再找第二大的，如果用競賽排序的方法，可以再使用 logn就可以找到了。 不過不知道怎麼證明 這是最小次數。

順便實現了一下 競賽排序。

1. public class TournamentSort {
4. private class Node//用node來存儲競賽排序過程中的節點，包括裡面的數據和數據在數組中的ID
5. {
6. public int data;
7. public int id;
9. public Node()
10. {
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. }
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算出來是為了做成滿二叉樹
61. Node[] nodes = new Node[nTreeSize];//競賽樹用數組存儲
62. //initialize the data
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. }
78. }
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);
99. }
103. }
104. }