注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

享受编码

    的乐趣

 
 
 

日志

 
 

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

2011-05-31 17:01:09|  分类: Java |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

转载:来自http://yiyickf.iteye.com/blog/1047010

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

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017