各种排序算法速度的比较！！不知道好不好拿来和大家分享下。。。。。有什么不好的大家多多包涵。。。

Question

本帖最后由 java2000_net 于 2008-08-04 17:34:37 编辑

Answer 1

package com.order.algorithm;
public class SelectionSort implements SortUtil.Sort {
  public void sort(int[] data) {
    int temp;
    for (int i = 0; i < data.length; i++) {
        int lowIndex = i;
        for (int j = data.length - 1; j > i; j--) {
          if (data[j] < data[lowIndex]) {
            lowIndex = j;
          }
        }
        SortUtil.swap(data,i,lowIndex);
    }
  } }
package com.order.algorithm;
public class ShellSort implements SortUtil.Sort{
  public void sort(int[] data) {
    for(int i=data.length/2;i>2;i/=2){
        for(int j=0;j<i;j++){
          insertSort(data,j,i);
        }
    }
    insertSort(data,0,1);
  }   /**
  * @param data
  * @param j
  * @param i
  */
  private void insertSort(int[] data, int start, int inc) {
    int temp;
    for(int i=start+inc;i<data.length;i+=inc){
        for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
          SortUtil.swap(data,j,j-inc);
        }
    }
  } }
package com.order.algorithm;public class Test {
public static void main(String[] args) {
int[] a = new int[1000];
long start1 = 0L, end1 = 0L, start2 = 0L, end2 = 0L, 
start3 = 0L, end3 = 0L, start4 = 0L, end4 = 0L,
start5 = 0L, end5 = 0L,start6 = 0L, end6 = 0L,
start7 = 0L, end7 = 0L,start8 = 0L, end8 = 0L;
QuickSort qs = new QuickSort();
ImprovedQuickSort iqs = new ImprovedQuickSort();
ShellSort ss = new ShellSort();
BubbleSort bs = new BubbleSort();
HeapSort hs = new HeapSort();
InsertSort is=new InsertSort();
MergeSort ms=new MergeSort();
SelectionSort sels=new SelectionSort();
System.out.println("随机产生的数组："); for (int i = 0; i <= 999; i++) {
a[i] = (int) (Math.random() * 10000);
System.out.print(a[i] + " ");
}
System.out.println();
System.out.println("----------------------------");
System.out.println("快速排序后的结果:");
start1 = System.nanoTime();
qs.sort(a);
for (int j = 0; j < a.length - 1; j++) {
//System.out.print(a[j] + " ");
}
end1 = System.nanoTime();
System.out.println("排序消耗时间:" + (end1 - start1));
System.out.println("----------------------------");
System.out.println("改进的快速排序后的结果:");
start2 = System.nanoTime();
iqs.sort(a);
for (int m = 0; m < a.length - 1; m++) {
//System.out.print(a[m] + " ");
}
end2 = System.nanoTime();
System.out.println("排序消耗时间:" + (end2 - start2));
System.out.println("-----------------------------");
System.out.println("Shell排序后的结果:");
start3 = System.nanoTime();
ss.sort(a);
for (int k = 0; k < a.length - 1; k++) {
//System.out.print(a[k] + " ");
}
end3 = System.nanoTime(); System.out.println("排序消耗时间:" + (end3 - start3));
System.out.println("------------------------------");
System.out.println("冒泡排序后的结果:");
start4 = System.nanoTime();
bs.sort(a);
for (int l = 0; l < a.length - 1; l++) {
//System.out.print(a[l] + " ");
}
end4 = System.nanoTime();
System.out.println("排序消耗时间:" + (end4 - start4));
System.out.println("------------------------------");
System.out.println("堆排序后的结果:");
start5 = System.nanoTime();
hs.sort(a);
for (int n = 0; n < a.length - 1; n++) {
//System.out.print(a[n] + " ");
}
end5 = System.nanoTime();
System.out.println("排序消耗时间:" + (end5 - start5));

System.out.println("------------------------------");
System.out.println("插入排序后的结果:");
start6 = System.nanoTime();
is.sort(a);
for (int p = 0; p < a.length - 1; p++) {
//System.out.print(a[p] + " ");
}
end6 = System.nanoTime();
System.out.println("排序消耗时间:" + (end6 - start6));

System.out.println("------------------------------");
System.out.println("归并排序后的结果:");
start7 = System.nanoTime();
ms.sort(a);
for (int q = 0; q < a.length - 1; q++) {
//System.out.print(a[q] + " ");
}
end7 = System.nanoTime();
System.out.println("排序消耗时间:" + (end7 - start7));

System.out.println("------------------------------");
System.out.println("选择排序后的结果:");
start8 = System.nanoTime();
ms.sort(a);
for (int r = 0; r < a.length - 1; r++) {
//System.out.print(a[r] + " ");
}
end8 = System.nanoTime();
System.out.println("排序消耗时间:" + (end8 - start8));

}}

Answer 2

测试结果3组：我把改进的快速排序去掉了 写得不好怕被笑话 嘿嘿
----------------------------
快速排序后的结果:
排序消耗时间:4232661
----------------------------
Shell排序后的结果:
排序消耗时间:2948978
------------------------------
冒泡排序后的结果:
排序消耗时间:5403200
------------------------------
堆排序后的结果:
排序消耗时间:5855493
------------------------------
插入排序后的结果:
排序消耗时间:190247
------------------------------
归并排序后的结果:
排序消耗时间:2044673
------------------------------
选择排序后的结果:
排序消耗时间:4272331
----------------------------
快速排序后的结果:
排序消耗时间:5580598
----------------------------
Shell排序后的结果:
排序消耗时间:1186184
------------------------------
冒泡排序后的结果:
排序消耗时间:6581563
------------------------------
堆排序后的结果:
排序消耗时间:5524725
------------------------------
插入排序后的结果:
排序消耗时间:191085
------------------------------
归并排序后的结果:
排序消耗时间:2033778
------------------------------
选择排序后的结果:
排序消耗时间:6960940
----------------------------
快速排序后的结果:
排序消耗时间:5541486
-----------------------------
Shell排序后的结果:
排序消耗时间:1292064
------------------------------
冒泡排序后的结果:
排序消耗时间:5262401
------------------------------
堆排序后的结果:
排序消耗时间:5606020
------------------------------
插入排序后的结果:
排序消耗时间:194997
------------------------------
归并排序后的结果:
排序消耗时间:1955277
------------------------------
选择排序后的结果:
排序消耗时间:6380420

Answer 3

缺少了2个
ImprovedQuickSort iqs = new ImprovedQuickSort();
//        ShellSort ss = new ShellSort();

Answer 4

原则上没用。1、各种排序算法的优劣，应该有专门的文章（技术文章和数学证明）说过，而不是仅仅几个小例子就可以证明的。2、Arrays.sort原则上可以适用于大多数情况。