`

排序算法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版

    七种排序算法Java版 以下是对七种排序算法Java版的详细解释: 1. 冒泡排序 冒泡排序是一种简单的排序算法,时间复杂度为O(n2),算法具有稳定性。冒泡排序的基本思想是:通过对数组的多次遍历,逐渐将最大(或最小...

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

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

    快速排序算法JAVA实现

    在Java中,我们可以创建一个名为`Qsort`的类来实现快速排序。这个类包含两个主要方法:`sort`和`partition`。`sort`方法是快速排序的递归入口,`partition`方法则是快速排序的核心,它负责将数组分为两部分,并返回...

    java版本排序算法

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

    Java各种排序算法代码.zip

    这个名为"Java各种排序算法代码.zip"的压缩包包含了一系列实现不同排序算法的Java源代码。排序算法是计算机科学中的基本概念,用于对一组数据进行排列。下面将详细讨论这些算法及其在Java中的实现。 1. 冒泡排序...

    Java常用8大排序算法

    ### Java常用八大排序算法详解 #### 一、直接插入排序 **基本思想:** 直接插入排序的基本思路是在要排序的一组数中,假设前面 (n-1) [n&gt;=2] 个数已经排好顺序,现在要把第 n 个数插入到前面的有序数列中,使得这 ...

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

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

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

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

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

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

    各类排序算法java的实现

    根据提供的文件信息,我们可以深入探讨几种不同的排序算法在Java中的实现。这些算法包括插入排序(Insert Sort)、冒泡排序(Bubble Sort)、选择排序(Selection Sort)以及希尔排序(Shell Sort)。接下来,我们将...

    数据结构java版 排序算法

    【数据结构与排序算法在Java中的应用】 在计算机科学中,数据结构是组织和存储数据的方式,而排序算法则是对这些数据进行排列的策略。在Java编程中,掌握各种排序算法对于提高程序效率至关重要。本篇文章将深入探讨...

    Java 快速排序算法

    Java 快速排序,目前来说效率很高的一种排序算法,好理解。

    三种线性排序算法Java实现

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

    常用排序算法总结(含Java代码)

    冒泡排序和快速排序是两种基础但广泛使用的数据排序算法。冒泡排序由于其简单直观的特性,易于理解和实现,而快速排序则以其较高的效率在数据量较大时展现出优势。 首先,让我们来看冒泡排序算法。冒泡排序通过重复...

    7大排序算法Java版

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

    JAVA排序算法集合

    以上介绍了Java排序算法中常见的几种方法及其变体。每种算法都有其特点和适用场景,例如当数据量较小时可以选择直接插入排序或直接选择排序;当数据量较大时,归并排序和快速排序则更为合适。理解这些算法的工作原理...

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

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

Global site tag (gtag.js) - Google Analytics