¿´ÍøÓѵÄÒ»µÀÌÚѶÃæÊÔÌâÓиÐ

10000+¸öÊý×ÖÖÓÕÒ³ötop100

Java´úÂë

1. import java.util.Arrays;
2. import java.util.Random;
4. public class Top100 {
5. private static Node head = null;
6. private static Node end = null;
7. private static Node tempNode = null;
8. private static Node node = null;
10. public static int[] getTop100(int[] inputArray) {
12. int result[] = new int[100];
13. int k = 100;
14. if (inputArray.length < 100) {
15. k = inputArray.length;
16. }
17. for (int i = 0; i < 100; ++i) {
18. result[i] = inputArray[i];
19. }
21. Arrays.sort(result);
23. for (int i = k - 1; i >= 0; i--) {
24. node = new Node(result[i], tempNode);
25. if (i == k - 1) {
26. head = node;
27. } else {
28. tempNode.right = node;
29. }
30. if (i == 0) {
31. end = node;
32. }else{
33. tempNode = node;
34. }
35. }
36. tempNode = end ;
39. for (int i = 100; i < inputArray.length; i++) {
40. int tempValue = inputArray[i];
41. if (tempValue <= end.value) {
42. continue;
43. }else{
44. tempNode = end;
45. setValue(inputArray[i]) ;
46. }
47. }
49. for (int i = 0; i < 100; i++) {
50. if (i == 0) {
51. node = head;
52. } else {
53. node = node.right;
54. }
55. result[i] = node.value;
56. }
58. return result;
60. }
62. private static void setValue(int tempValue) {
63. if (tempNode.value < tempValue) {
64. tempNode = tempNode.left;
65. //×î´óµÄ
66. if(tempNode==null){
67. node = new Node(head,tempValue );
68. head.left = node ;
69. head = node ;
70. removeEnd() ;
71. }else{
72. setValue(tempValue);
73. }
74. } else if (tempNode.value != tempValue) {
75. node = new Node(tempValue, tempNode);
76. //ÒªÌæ´úend
77. if(tempNode.right==end){
78. end.left.right = node ;
79. end = node ;
80. }else{
81. try {
82. tempNode.right.left = node;
83. } catch (Exception e) {
84. // TODO Auto-generated catch block
85. System.err.println(tempNode.right) ;
86. e.printStackTrace() ;
87. System.exit(0) ;
88. }
89. tempNode.right = node;
90. removeEnd() ;
91. }
92. }
93. }
95. private static void removeEnd(){
96. end = end.left ;
97. end.right = null ;
98. }
100. public static void main(String[] args) {
102. int numberCount = 1000000;
104. int maxNumber = numberCount;
106. int inputArray[] = new int[numberCount];
108. Random random = new Random();
110. for (int i = 0; i < numberCount; ++i) {
112. inputArray[i] = Math.abs(random.nextInt(maxNumber));
114. }
116. System.out.println("Sort begin...");
118. long current = System.currentTimeMillis();
120. int[] result = Top100.getTop100(inputArray);
122. System.out.println(System.currentTimeMillis() - current + "ms");
124. for (int i = 0; i < result.length; ++i) {
126. System.out.print(i + "." + result[i] + ",");
128. }
130. }
132. }
134. class Node {
135. protected int value;
136. protected Node left;
137. protected Node right;
139. public Node(int value) {
140. this.value = value;
141. }
143. public Node(int value, Node left) {
144. this.value = value;
145. this.left = left;
146. }
148. public Node(Node right, int value) {
149. this.right = right;
150. this.value = value;
151. }
152. }