大鱼

排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序

先推荐一篇关于排序算法的文章:http://www.cppblog.com/guogangj/archive/2009/11/13/100876.html

本文思路部分来源于上篇文章,但测得的结果似乎不大相同,不知是因为java的缘故还是因为我算法的缘故,欢迎拍砖。

复习排序,顺便比下各种算法的速度,榜单如下:

1、冒泡排序

2、简单选择排序

3、直接插入排序

4、折半插入排序

5、希尔排序

6、堆排序

7、归并排序

8、快速排序

当然这是慢速排行,哈哈~~

直接上图:单位毫秒

数量

冒泡排序

简单选择排序

直接插入排序

折半插入排序

希尔排序

堆排序

归并排序

快速排序

10000

1578

1250

672

250

0

15

16

0

15000

3453

2765

1563

531

16

15

16

0

20000

6140

4547

2453

828

16

16

15

16

25000

10079

7171

3969

1313

31

16

15

16

30000

14641

10313

5578

1906

31

31

16

31

35000

20141

14328

7890

2563

31

31

32

15

40000

25766

18359

10094

3422

47

31

31

32

45000

32469

24063

13062

4359

47

47

31

47

由于"希尔排序","堆排序","归并排序","快速排序"太快,以至于在上图几乎是条直线,故有了下面转为他们准备的加强版

数量

希尔排序

堆排序

归并排序

快速排序

100000

172

140

110

93

200000

469

406

235

234

300000

812

703

422

375

400000

1125

1031

516

531

500000

1406

1282

719

656

600000

1828

1703

860

859

700000

2531

2063

1000

968

800000

2735

2453

1140

1188

900000

3047

2843

1391

1266

1000000

3375

3187

1516

1422

1100000

3922

3500

1625

1609

1200000

4421

3954

1969

1812

1300000

4797

4422

2000

1953

1400000

5391

4797

2547

2094

1500000

5437

5219

2625

2328

1600000

6203

5546

2469

2485

1700000

6532

5953

2844

2672

1800000

7125

6421

2984

2844

补上代码:

Java代码 收藏代码
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.List;
  4. /**
  5. * 插入排序:直接插入排序、折半插入排序和系尔排序
  6. * 交换排序:冒泡排序和快速排序
  7. * 选择排序:简单选择排序和堆排序
  8. * 归并排序:归并排序
  9. *
  10. * 基本思想
  11. * 插入排序:将第N个记录插入到前面(N-1)个有序的记录当中。
  12. * 交换排序:按照某种顺序比较两个记录的关键字大小,然后根据需要交换两个记录的位置。
  13. * 选择排序:根据某种方法选择一个关键字最大的记录或者关键字最小的记录,放到适当的位置。
  14. *
  15. * 排序方法比较
  16. * 排序方法 平均时间 最坏时间 辅助存储
  17. * 直接插入排序 O(N2) O(N2) O(1)
  18. * 起泡排序 O(N2) O(N2) O(1)
  19. * 快速排序 O(Nlog2N) O(N2) O(Nlog2N)
  20. * 简单选择排序 O(N2) O(N2) O(1)
  21. * 堆排序 O(Nlog2N) O(Nlog2N) O(1)
  22. * 归并排序 O(Nlog2N) O(Nlog2N) O(n)
  23. * 基数排序 O(d(n+radix)) O(d(n+radix)) O(radix)
  24. *
  25. *
  26. *
  27. * @author Administrator
  28. *
  29. */
  30. public class SortTest {
  31. public static void main(String[] args)throws Exception {
  32. //测试排序是否正确
  33. //String[] testErr=new String[]{"冒泡排序","简单选择排序","直接插入排序","折半插入排序","系尔排序","堆排序","归并排序","快速排序"};
  34. //new SortTest().testErr(testErr);
  35. //排序1(全部)
  36. String[] strs=new String[]{"冒泡排序","简单选择排序","直接插入排序","折半插入排序","希尔排序","堆排序","归并排序","快速排序"};
  37. new SortTest().test(strs,10000,50000,5000);
  38. //排序2(加强)
  39. String[] strs2=new String[]{"希尔排序","堆排序","归并排序","快速排序"};
  40. new SortTest().test(strs2,100000,1900000,100000);
  41. }
  42. private void testErr(String[] strings) throws Exception{
  43. //System.out.println(Arrays.toString(old));
  44. System.out.println(Arrays.toString(strings));
  45. Number[] old=getRundom(50);
  46. Integer[] oo={1,2,3,3,2,21,5,6,7,78,5,65,8,7,6,6,6,6,6,9,56544,354,32,4,456,8,89,-9,0,3,243,-321,321,-3,-2,21};
  47. old=oo;
  48. for(String s:strings){
  49. Number[] testNum=Arrays.copyOf(old, old.length);
  50. long begin=System.currentTimeMillis();
  51. SortTest.class.getMethod(s, Number[].class).invoke(this, (Object)testNum);
  52. long end=System.currentTimeMillis();
  53. System.out.println(s+":"+(end-begin)+"\t");
  54. System.out.println(Arrays.toString(testNum));
  55. }
  56. System.out.println();
  57. }
  58. private void test(String[] strings,long begin,long end,long step) throws Exception{
  59. System.out.print("数量\t");
  60. for(String str:strings){
  61. System.out.print(str+"\t");
  62. }
  63. System.out.println();
  64. for(long i=begin;i<end;i=i+step){
  65. System.out.print(i+"个\t");
  66. Number[] old=getRundom(i);
  67. for(String s:strings){
  68. Number[] testNum=Arrays.copyOf(old, old.length);
  69. long beginTime=System.currentTimeMillis();
  70. SortTest.class.getMethod(s, Number[].class).invoke(this, (Object)testNum);
  71. long endTime=System.currentTimeMillis();
  72. System.out.print((endTime-beginTime)+"\t");
  73. //System.out.println(Arrays.toString(testNum));
  74. }
  75. System.out.println();
  76. }
  77. }
  78. private static Integer[] getRundom(long num) {
  79. List<Integer> list=new ArrayList<Integer>();
  80. for(long i=0;i<num;i++){
  81. int k;
  82. if(Math.random()>0.5){
  83. k=(int)(Math.random()*Integer.MAX_VALUE);
  84. }else{
  85. k=(int)(Math.random()*Integer.MIN_VALUE);
  86. }
  87. list.add(k);
  88. }
  89. return list.toArray(new Integer[list.size()]);
  90. }
  91. /**
  92. * 插入排序————直接插入排序
  93. * @param data
  94. */
  95. public static void 直接插入排序(Number[] data)
  96. {
  97. Number tmp=null ;
  98. for(int i=1;i<data.length;i++){
  99. tmp = data[i];
  100. int j=i-1;
  101. while(j>=0 && tmp.doubleValue()<data[j].doubleValue()){
  102. data[j+1]=data[j];
  103. j--;
  104. }
  105. data[j+1]=tmp;
  106. }
  107. }
  108. /**
  109. * 插入排序————折半插入排序
  110. * @param data
  111. */
  112. public static void 折半插入排序(Number[] data)
  113. {
  114. Number tmp=null ;
  115. for(int i=1;i<data.length;i++){
  116. tmp = data[i];
  117. int smallpoint=0;
  118. int bigpoint=i-1;
  119. while(bigpoint>=smallpoint){
  120. int mid=(smallpoint+bigpoint)/2;
  121. if(tmp.doubleValue()>data[mid].doubleValue()){
  122. smallpoint=mid+1;
  123. }else{
  124. bigpoint=mid-1;
  125. }
  126. }
  127. for(int j=i;j>smallpoint;j--){
  128. data[j]=data[j-1];
  129. }
  130. data[bigpoint+1]=tmp;
  131. }
  132. }
  133. /**
  134. * 插入排序————希尔排序
  135. * @param data
  136. */
  137. public static void 希尔排序(Number[] data)
  138. {
  139. int span=data.length/7;
  140. if(span==0)span=1;
  141. while(span>=1){
  142. for(int i=0;i<span;i++){
  143. for(int j=i;j<data.length;j=j+span){
  144. //组内直接插入排序
  145. int p = j-span;
  146. Number temp = data[j];
  147. while( p >=0 && data[p].doubleValue() > temp.doubleValue()){
  148. data[p+span] = data[p];
  149. p -=span;
  150. }
  151. data[p + span] = temp;
  152. }
  153. }
  154. span=span/2;
  155. }
  156. }
  157. /**
  158. * 交换排序————冒泡排序
  159. *
  160. * @param data
  161. */
  162. public static void 冒泡排序(Number[] data)
  163. {
  164. for (int i = 0; i < data.length; i++) {
  165. //将相邻两个数进行比较,较大的数往后冒泡
  166. for (int j = 0; j < data.length - i-1; j++) {
  167. if (data[j].doubleValue()> data[j + 1].doubleValue()) {
  168. //交换相邻两个数
  169. swap(data, j, j + 1);
  170. }
  171. }
  172. }
  173. }
  174. /**
  175. * 交换排序————快速排序
  176. * @param data
  177. */
  178. public static void 快速排序(Number[] data)
  179. {
  180. QuickSort(data,0,data.length-1);
  181. }
  182. private static void QuickSort(Number[] data, int begin, int end) {
  183. // System.out.println(begin+":"+end);
  184. if(begin<end){
  185. //取中点
  186. int mid=(begin+end)/2;
  187. if(data[end].doubleValue()<data[begin].doubleValue()){
  188. swap(data, end, begin);
  189. }
  190. if(data[end].doubleValue()<data[mid].doubleValue()){
  191. swap(data, end, mid);
  192. }
  193. if(data[mid].doubleValue()<data[begin].doubleValue()){
  194. swap(data, mid, begin);
  195. }
  196. swap(data, mid, begin);
  197. // System.out.println(Arrays.toString(Arrays.copyOfRange(data, begin, end)) );
  198. int min=begin+1;
  199. int big=end;
  200. while(true){
  201. while(min<big && data[min].doubleValue()<data[begin].doubleValue()){min++;}
  202. while(min<big && data[big].doubleValue()>=data[begin].doubleValue()){big--;}
  203. if(min>=big){
  204. break;
  205. }
  206. swap(data, min, big);
  207. }
  208. if(data[begin].doubleValue()>data[min].doubleValue()){
  209. swap(data, begin, min);
  210. }
  211. if(min>1)
  212. QuickSort(data,begin,min-1);
  213. //if(min<end)
  214. QuickSort(data,min,end);
  215. }
  216. }
  217. /**
  218. * 选择排序————简单选择排序
  219. * @param data
  220. */
  221. public static void 简单选择排序(Number[] data)
  222. {
  223. for (int i = 0; i < data.length-1; i++) {
  224. int smallPoint=i;
  225. for (int j = i+1; j < data.length; j++) {
  226. if (data[smallPoint].doubleValue()> data[j].doubleValue()) {
  227. smallPoint=j;
  228. }
  229. }
  230. swap(data, i, smallPoint);
  231. }
  232. }
  233. /**
  234. * 选择排序————堆排序
  235. * @param data
  236. */
  237. public static void 堆排序(Number[] data)
  238. {
  239. int n = data.length;
  240. for(int i=n/2;i>=0;i--){
  241. keepHeap(data, n, i);
  242. }
  243. while (n > 0) {
  244. swap(data, 0, n-1);
  245. keepHeap(data, --n, 0);
  246. }
  247. }
  248. private static void keepHeap(Number[] a, int n, int i) {
  249. Number x = a[i];
  250. int j = 2 * i + 1;
  251. while (j <= n - 1) {
  252. if (j < n - 1 && a[j].doubleValue() < a[j + 1].doubleValue())
  253. ++j;
  254. if (a[j].doubleValue() > x.doubleValue()) {
  255. a[i] = a[j];
  256. i = j;
  257. j = 2 * i ;
  258. } else{
  259. break;
  260. }
  261. }
  262. a[i] = x;
  263. }
  264. /**
  265. * 归并排序法————归并排序
  266. * @param data
  267. */
  268. public static void 归并排序(Number[] data)
  269. {
  270. Number[] result = merge_sort(data,0,data.length-1);
  271. for(int i=0;i<result.length;i++){
  272. data[i]=result[i];
  273. }
  274. }
  275. private static Number[] merge_sort(Number[] array, int start, int end){
  276. Number[] result = new Number[end-start+1];
  277. if(start< end){
  278. int mid= (start+end)/2;
  279. Number[] left= merge_sort(array, start, mid);
  280. Number[] right = merge_sort(array, mid+1, end);
  281. result= merge(left,right);
  282. } else if (start == end) {
  283. result[0] = array[start];
  284. return result;
  285. }
  286. return result;
  287. }
  288. private static Number[] merge(Number[] left, Number[] right) {
  289. Number[] result = new Number[left.length+right.length];
  290. int i=0;
  291. int j=0;
  292. int k=0;
  293. while(i< left.length&&j< right.length){
  294. if(left[i].doubleValue()< right[j].doubleValue()){
  295. result[k++] = left[i++];
  296. }else{
  297. result[k++] = right[j++];
  298. }
  299. }
  300. while(i< left.length){
  301. result[k++] = left[i++];
  302. }
  303. while (j< right.length) {
  304. result[k++]= right[j++];
  305. }
  306. return result;
  307. }
  308. /**
  309. * 交换数组中指定的两元素的位置
  310. * @param data
  311. * @param x
  312. * @param y
  313. */
  314. private static void swap(Number[] data, int x, int y) {
  315. Number temp = data[x];
  316. data[x] = data[y];
  317. data[y] = temp;
  318. }
  319. }

posted on 2011-10-06 23:34 大鱼 阅读(807) 评论(1)  编辑  收藏 所属分类: 软件工程

评论

# re: 排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序 2011-10-07 19:35 安多

收藏了  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航: