排序的效率问题~
小弟不才,只会三种排序(选择排序,冒泡排序,插入排序),也不知道哪种排序效率最高.于是就做个小测试.

1. public class Test3 {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                
   
5.                 long start = System.currentTimeMillis();
   
6.                 for(int i=0;i<10000000;i++){
   
7.                         int[] arr = { 122, 342, 53, 14, 333, 523, 888, 77, 1, 664 };
   
8. //                        insertSort(arr);
   
9. //                        bubbleSort(arr);
   
10. //                        selectSort(arr);
    
11.                 }
    
12.                 System.out.println(System.currentTimeMillis() - start);
    
13.         }
    
14. 
    
15.         /**
    
16.          * 插入排序
    
17.          */
    
18.         static void insertSort(int[] arr) {
    
19.                 for (int i = 1; i < arr.length; i++) {
    
20.                         int pos = i;
    
21.                         while (pos > 0 && arr[pos] < arr[pos - 1]) {
    
22.                                 int temp = arr[pos];
    
23.                                 arr[pos] = arr[pos - 1];
    
24.                                 arr[pos - 1] = temp;
    
25.                                 pos--;
    
26.                         }
    
27.                 }
    
28.         }
    
29. 
    
30.         /**
    
31.          * 冒泡排序
    
32.          */
    
33.         static void bubbleSort(int[] arr) {
    
34.                 for (int i = 0; i < arr.length - 1; i++) {
    
35.                         for (int j = 0; j < arr.length - 1 - i; j++) {
    
36.                                 if (arr[j] > arr[j + 1]) {
    
37.                                         int temp = arr[j];
    
38.                                         arr[j] = arr[j + 1];
    
39.                                         arr[j + 1] = temp;
    
40.                                 }
    
41.                         }
    
42.                 }
    
43.         }
    
44. 
    
45.         /**
    
46.          * 选择排序
    
47.          */
    
48.         static void selectSort(int[] arr) {
    
49.                 for (int i = 0; i < arr.length - 1; i++)
    
50.                 {
    
51.                         int pos = i;
    
52.                         for (int j = i + 1; j < arr.length; j++) {
    
53.                                 if (arr[j] < arr[pos])
    
54.                                         pos = j;
    
55.                         }
    
56.                         int temp = arr[i];
    
57.                         arr[i] = arr[pos];
    
58.                         arr[pos] = temp;
    
59.                 }
    
60.         }
    
61. }
    

复制代码

大家可以复制一下,然后打开上面被注掉的方法.测试一下, 经过我多次测试,插入排序速度是最快的.

我不太明白里面的原因...有谁懂???

效率差排序在比较的次数以及交换的频率比插入排序要多

冒泡排序：
对于n个数据的数组，共进行n-1趟排序，第一趟排序中有n-1次比较，第二趟有n-2次比较，依次类推，最后一趟有1次比较
（n-1）+（n-2）...+1 = n *(n-1)/2    总共进行了n*n/2次比较
如果数据是随机的，大概有一半数据需要交换，则交换的次数为n*n/4，在最坏的情况下，即初始是逆序的，每次都需要交换。
交换和比较次数都和n的平方成正比，时间复杂度为O（n*n）

选择排序：
和冒泡排序相比，执行了相同的比较次数n *(n-1)/2，但对于n个数据，只需要少于n次的交换。
时间复杂度为O（n*n），选择排序比冒泡排序快，因为它进行的交换少的多，当n值较小时，特别是交换的时间大于比较时间，选择排序是相当快

的。

插入排序：
在第一趟排序中，最多比较1次，第二趟最多比较2次，依次类推，最后一趟最多比较n-1次，因此有（n-1）+（n-2）...+1 = n *(n-1)/2，
然而，在每一趟发现插入点之前，平均只有全体数据项的一半真的进行了比较，除以2得到n *(n-1)/4
复制的次数大致等于比较的次数，即n *(n-1)/4，然而，一次复制与一次交换的耗时不同，所以，相对于随机数据，这个算法比冒泡排序快一倍

，比选择排序略快。
对于基本有序的数据，只需要O（n）的时间，插入排序对于基本有序的数据是一个简单有效的方法。

张运 发表于 2013-10-13 09:09
冒泡排序：
对于n个数据的数组，共进行n-1趟排序，第一趟排序中有n-1次比较，第二趟有n-2次比较，依次类推 ...

神回复...NB...!!