<rt id="bn8ez"></rt>
<label id="bn8ez"></label>
  • 

    • <span id="bn8ez"></span>
    

    <label id="bn8ez"><meter id="bn8ez"></meter></label>
    

    
    

    




    







												


        


    


    大魚
    

    

    




    
	
					
	
    
		
    
			排序算法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.  * 基本思想  
    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. }  
    
		
    
			posted on 2011-05-24 23:58 大魚 閱讀(1803) 評論(0)  編輯  收藏  所屬分類: j2se 
		
    
	
    
	
	





    
	    
    




    








    

				

    



    







    
        
	



主站蜘蛛池模板：
亚洲人色婷婷成人网站在线观看|
亚洲国产美国国产综合一区二区|
精品国产免费人成网站|
亚洲av无码国产精品色午夜字幕
|
亚洲av成人片在线观看|
亚洲精品第一国产综合精品99|
久久99精品免费视频|
一本色道久久88亚洲精品综合
|
色窝窝免费一区二区三区|
污网站免费在线观看|
亚洲综合图片小说区热久久|
国产区卡一卡二卡三乱码免费|
国内精品免费久久影院|
亚洲不卡影院午夜在线观看|
久久久久亚洲av毛片大
|
亚洲AV无码码潮喷在线观看|
免费观看a级毛片|
日韩免费在线观看视频|
精品在线免费视频|
亚洲冬月枫中文字幕在线看|
国产亚洲美日韩AV中文字幕无码成人
|
一级毛片a女人刺激视频免费
|
亚洲暴爽av人人爽日日碰|
亚洲国产精品久久66|
免费人成视频x8x8入口|
青青青国产在线观看免费网站|
久久免费99精品国产自在现线|
亚洲一卡2卡3卡4卡5卡6卡
|
亚洲欧洲春色校园另类小说|
亚洲日韩精品无码专区网站
|
亚洲AV无一区二区三区久久|
全部免费a级毛片|
岛国av无码免费无禁网站|
一级毛片免费观看|
久久国产乱子伦精品免费午夜|
亚洲a∨国产av综合av下载|
亚洲码在线中文在线观看|
亚洲va无码va在线va天堂|
亚洲精品专区在线观看|
国产午夜影视大全免费观看|
免费人成在线视频|