`

排序算法java版(转载)

阅读更多

转载自 ---- 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.            }  

分享到:
评论

相关推荐

    堆排序算法 java

    堆排序算法 java

    各种排序算法比较(java实现)

    本文将详细探讨标题所提及的几种排序算法:合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序,并结合Java语言的实现进行解析。 1. **合并排序(Merge Sort)**: 合并排序是一种基于分治策略的排序算法...

    各种排序算法java源代码

    本资源提供了Java语言实现的五种经典排序算法:冒泡排序、快速排序、插入排序、选择排序以及测试程序。下面将详细介绍这四种排序算法的原理、特点以及Java实现的关键点。 1. **冒泡排序**: 冒泡排序是一种简单...

    9大排序算法java版

    "9大排序算法java版"这个压缩包可能包含了以下九种经典的排序算法的Java实现: 1. 冒泡排序(Bubble Sort):这是一种简单的排序算法,通过重复遍历待排序的数组,依次比较相邻元素并交换位置来完成排序。时间...

    常见的七大排序算法Java实现.zip

    本压缩包"常见的七大排序算法Java实现.zip"包含了七种经典的排序算法在Java语言中的实现。尽管文件列表中并未明确列出每种排序算法的名称,但根据常规,这七大排序算法可能包括冒泡排序、插入排序、选择排序、快速...

    快速排序算法的java实现

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法(Divide and Conquer),通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的...

    快速排序算法java代码

    "快速排序算法java代码" 快速排序算法是由Tony Hoare在1960年提出的一种排序算法,它的平均时间复杂度为O(n log n),是目前最快的排序算法之一。下面我们将详细地讲解快速排序算法的java代码实现。 快速排序算法的...

    七种排序算法Java版

    ### 七种排序算法Java版 #### 内容概述 本文档主要介绍了七种常见的排序算法在Java中的实现,包括冒泡排序、选择排序、快速排序、插入排序、希尔排序、归并排序以及堆排序。这些算法是计算机科学中基础且重要的组成...

    基于java语言十大经典排序算法

    **基于Java语言十大经典排序算法** 排序算法是计算机科学中不可或缺的一部分,特别是在数据处理和算法设计领域。在Java编程中,理解并掌握各种排序算法能够帮助开发者提高代码效率,优化性能。以下是Java语言中十大...

    java版本排序算法

    ### Java版本排序算法详解 #### 插入排序 插入排序是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。在Java中,我们可以创建一个`...

    七种排序算法Java版性能比较+Java实现.doc

    本文将详细分析七种常见的Java排序算法:冒泡排序、选择排序、快速排序、插入排序、希尔排序、归并排序和堆排序,并探讨它们在不同条件下的性能表现。 1. **冒泡排序**: - 时间复杂度:平均和最坏情况下都是O(n^2...

    IT面试笔试-各种排序算法Java实现

    【IT面试笔试中的排序算法Java实现】 在IT面试和笔试中,掌握各种排序算法的实现是必不可少的技能。本文将详细介绍几种经典的排序算法,并提供Java语言的实现代码,包括冒泡排序、插入排序、选择排序和快速排序。...

    常用的排序算法(java实现),附带一个PPT动画演示、详解了其中三种

    除了插入排序和希尔排序,压缩包中还可能包含了其他几种常见的排序算法的Java实现,如冒泡排序、快速排序、选择排序、归并排序和堆排序等。每种排序算法都有其特定的适用场景和性能特点。例如,冒泡排序虽然简单,但...

    JAVA冒泡排序和快速排序算法

    在编程领域,排序算法是数据结构与算法学习中的基础部分,尤其在JAVA中,掌握不同的排序算法对于提高程序效率至关重要。本节将深入探讨两种常见的排序算法:冒泡排序和快速排序。 首先,我们来详细讲解冒泡排序。...

    三种线性排序算法Java实现

    本资源提供的Java实现包括了三种线性排序算法:桶排序(Bucket Sort)、基数排序(Radix Sort)和计数排序(Counting Sort)。这三种算法在特定条件下可以达到线性的平均或最好时间复杂度,效率相对较高。 1. **桶...

    7大排序算法Java版

    在编程领域,排序算法是计算机科学的基础之一,尤其在Java这样的多用途编程语言中,对数据进行高效排序是至关重要的。本资源包含了七大经典排序算法的Java实现,这对于学习、复习或面试准备都非常有价值。接下来,...

    Java所有排序算法大全

    在编程领域,排序算法是计算机科学中的核心概念,特别是在Java这样的高级编程语言中。本文将深入探讨Java中常见的几种排序算法,包括它们的工作原理、优缺点以及如何在实际编程中应用。 首先,我们来看`BubbleSort...

    java排序算法插入选择冒泡

    java排序算法java排序算法插入选择冒泡java排序算法插入选择冒泡

    java实现数据结构常见排序算法及详解

    ### Java 实现数据结构常见排序算法及详解 #### 排序算法概述 排序算法是计算机科学中的基础概念之一,主要用于将一系列数据按照特定规则进行排列。根据数据处理方式的不同,排序算法大致分为两大类:比较排序与非...

    java常用的7大排序算法汇总

    ### Java常用的七大排序算法 #### 1. 插入排序算法 插入排序是一种简单直观的排序算法。它的基本思想是:对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 - **算法步骤**: 1. 将第一待排序...

Global site tag (gtag.js) - Google Analytics