冒泡排序,插入排序,快速排序java实现和效率比较

冒泡排序，插入排序，快速排序java实现和效率比较

从测试结果看，冒泡算法明显不是一般的慢，10万数组的时候冒泡要4秒多，所以就百万就没用冒泡继续测试。

插入排序在结果中看来是最优的，为了方便比较，插入排序分别用了数组和list

综合结果：

list插入排序> 数组插入排序> 快速排序> > 冒泡排序

输出结果：

******万级测试******

快速排序耗时：

5

list插入排序耗时：

1

数组插入排序耗时：

1

冒泡排序耗时：

372

******百万测试******

快速排序耗时：

118

list插入排序耗时：

1

数组插入排序耗时：

12

[java] view plaincopyprint?

1. import java.util.ArrayList;

2. import java.util.List;

3. import java.util.Random;

4.

5.

6. public class SortPractice {

7.

8. public static void main(String[] args){

9. System.out.println("******正确性测试******");

10. Random random = new Random();

11. SortPractice sp = new SortPractice ();

12. int[] nums = new int[10];

13. //生成随机整数数组

14. for(int i = 0;i

15. nums[i] = random.nextInt();

16. }

17. //输出未排序的数组

19. //输出排序后的数组

20. sp.println(sp.sort(nums));

21. sp.println(sp.insertSort(nums));

22. sp.println(sp.insertSort(sp.toList(nums)));

23. sp.println(sp.quickSort(sp.toList(nums)));

24.

25. System.out.println("******万级测试******");

26. //万级排序时间测试

27. nums = new int[10000];

28. //生成随机整数数组

29. for(int i = 0;i

30. nums[i] = random.nextInt();

31. }

32.

33. List list = sp.toList(nums);

34. long begin = System.currentTimeMillis();

35. sp.quickSort(list);

36. System.out.println("快速排序耗时：\r\n"+(System.currentTimeMillis()-begin));

37.

38. list = sp.toList(nums);

39. begin = System.currentTimeMillis();

41. System.out.println("list插入排序耗时：\r\n"+(System.currentTimeMillis()-begin));

42.

43. begin = System.currentTimeMillis();

44. sp.insertSort(nums);

45. System.out.println("数组插入排序耗时：\r\n"+(System.currentTimeMillis()-begin));

46.

47. begin = System.currentTimeMillis();

48. sp.sort(nums);

49. System.out.println("冒泡排序耗时：\r\n"+(System.currentTimeMillis()-begin));

50.

51. System.out.println("******百万测试******");

52. //百万级，排序时间测试

53. nums = new int[1000000];

54. //生成随机整数数组

55. for(int i = 0;i

56. nums[i] = random.nextInt();

57. }

58.

59. list = sp.toList(nums);

60. begin = System.currentTimeMillis();

61. sp.quickSort(list);

62. System.out.println("快速排序耗时：\r\n"+(System.currentTimeMillis()-begin));

63.

64. list = sp.toList(nums);

65. begin = System.currentTimeMillis();

66. sp.insertSort(list);

67. System.out.println("list插入排序耗时：\r\n"+(System.currentTimeMillis()-begin));

68.

69. begin = System.currentTimeMillis();

70. sp.insertSort(nums);

71. System.out.println("数组插入排序耗时：\r\n"+(System.currentTimeMillis()-begin));

72. }

73.

74. /**

75. * 冒泡排序

76. * @param nums

77. * @return

78. */

79. public int[] sort(int[] nums){

80. int temp = 0;

81. for(int i = 0; i < nums.length-1; i++){

82. for(int j = i+1 ;j < nums.length; j++){

83. if(nums[j]>nums[i]){

85. nums[i] = nums[j];

86. nums[j] = temp;

87. }

88. }

89. }

90. return nums;

91. }

92.

93. /**

94. * 插入排序

95. * @param nums

96. * @return

97. */

98. public int[] insertSort(int[] nums){

99. int temp ;

100. for(int i = 1;i

102. temp = nums[i];

103. while(j>=0&&temp>nums[j]){ 104. temp = nums[j];

105. nums[j] = nums[i];

107. j--;

108. }

109. }

110.

111. return nums;

112. }

113. /**

114. * list插入排序

115. * @param nums

116. * @return

117. */

118. public List insertSort(List list){ 119. int temp ;

120. for(int i = 1;i

121. int j = i-1;

122. temp = list.get(i);

123. while(j >= 0 && temp > list.get(j)){

124. temp = list.get(j);

125. list.set(j,list.get(i));

126. list.set(i,list.get(j));

127. j--;

128. }

129. if(i>=1000) break;

130. }

131.

132. return list;

133. }

134.

135. /**

136. * 快速排序法

137. * @param nums

138. * @return

139. */

140. public List quickSort(List list){ 141. Integer mid = list.get(new Random().nextInt(list.size())); 142. mid = list.get(5);

143. List small = new ArrayList(); 144. List big = new ArrayList();

145.

146. for(int i = 0; i < list.size(); i++){

147. if(list.get(i)<=mid){

148. small.add(list.get(i));

149. }else{

150. big.add(list.get(i));

151. }

152. }

153. list.clear();

154. if(list.size()>2){

155. list.addAll(quickSort(big));

156. list.addAll(quickSort(small));

157. }else{

158. list.addAll(big);

159. list.addAll(small);

160. }

161. return list;

162. }

163.

164. /**

165. * 数组转list

166. * @param nums

167. * @return

168. */

169. public List toList(int[] nums){ 170. List list = new ArrayList(); 171. for(int i = 0; i < nums.length; i++){

172. list.add(nums[i]);

173. }

174. return list;

175. }

176. /**

177. * 打印数组

178. * @param nums

179. */

180. public void println(int[] nums){ 181. System.out.println("-----");

182. for(int i = 0;i

184. }

185. }

186.

187.

188. /**

189. * 打印list

190. * @param list

191. */

192. private void println(List list) { 193. System.out.println("---------");

194. for(Integer obj:list){ 195. System.out.println(obj); 196. }

197. }

198.

199. }