插入排序、归并排序、快速排序的比较

清疚 2022-04-15 05:11 309阅读 0赞

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70

为了获取每种排序算法实际的运行时间，我们可以为每种排序算法创建一个类，通过测试类调用它们，用Java自带的System.nanoTime()来获取算法运行的时间（1微秒=1000纳秒）。

整个过程需要以下API：

  1. /* 返回 v<w */
  2. private static boolean less(Comparable v, Comparable w){
  3.         return v.compareTo(w)<0;
  4.     }
  6. /* 交换a[i]与a[j]的位置 */
  7. private static void exch(Comparable[] a, int i, int j){
  8.         Comparable temp = a[i];
  9.         a[i] = a[j];
  10.         a[j] = temp;
  11.     }

插入排序：

  1. /* 插入排序 InsertSort */
  2. public class IS {
  3.     private static long S = 0;
  4.     public static void sort(Double[] a){
  5.         int N = a.length;
  6.         for (int i = 1; i < N; i++){
  7.             for (int j = i; j > 0 && less(a[j], a[j-1]); j--){
  8.                 exch(a, j, j-1);
  9.             }
  10.         }
  11.     }
  12. }

自顶向下归并排序：

  1. /* 自顶向下归并排序 Top-DownMergeSort */
  2. public class TDM {
  3.     private static Comparable[] aux;
  4.     public static void merge(Comparable[] a, int lo, int mid, int hi){
  5.         int i=lo, j=mid+1;
  6.         for (int k=lo; k<=hi; k++)
  7.             aux[k]=a[k];
  9.         for (int k=lo; k<=hi; k++){
  10.             if (i>mid)
  11.                 a[k]=aux[j++];
  12.             else if (j>hi)
  13.                 a[k]=aux[i++];
  14.             else if (less(aux[j], aux[i]))
  15.                 a[k]=aux[j++];
  16.             else 
  17.                 a[k]=aux[i++];
  18.         }
  19.     }
  21.     public static void sort(Comparable[] a){
  22.         aux=new Comparable[a.length];
  23.         sort(a, 0, a.length-1);
  24.     }
  26.     private static void sort(Comparable[] a, int lo, int hi){
  27.         if (hi<=lo)
  28.             return;
  29.         int mid=lo+(hi-lo)/2;
  30.         sort(a, lo, mid);
  31.         sort(a, mid+1, hi);
  32.         merge(a, lo, mid, hi);
  33.     }    
  34. }

自底向上归并排序

  1. /* 自底向上归并排序 Bottom-UpMergeSort */
  2. public class BUM {
  3.     private static Comparable[] aux;
  4.     public static void merge(Comparable[] a, int lo, int mid, int hi){
  5.         int i=lo, j=mid+1;
  6.         for (int k=lo; k<=hi; k++)
  7.             aux[k]=a[k];
  9.         for (int k=lo; k<=hi; k++){
  10.             if (i>mid)
  11.                 a[k]=aux[j++];
  12.             else if (j>hi)
  13.                 a[k]=aux[i++];
  14.             else if (less(aux[j], aux[i]))
  15.                 a[k]=aux[j++];
  16.             else 
  17.                 a[k]=aux[i++];
  18.         }
  19.     }
  21.     public static void sort(Comparable[] a){
  22.         int N=a.length;
  23.         aux=new Comparable[N];
  24.         for (int sz=1; sz<N; sz=sz+sz)
  25.             for (int lo=0; lo<N-sz; lo+=sz+sz)
  26.                 merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
  27.     }
  28. }

随机快速排序

  1. /* 随机快速排序 RandomQuickSort */
  2. import edu.princeton.cs.algs4.StdRandom;
  3. public class RQ {
  4.     private static int partition(Comparable[] a, int lo, int hi){
  5.         int i=lo, j=hi+1;
  6.         while (true){
  7.             while (less(a[++i],a[lo]))
  8.                 if (i==hi)
  9.                     break;
  10.             while (less(a[lo], a[--j]))
  11.                 if (j==lo)
  12.                     break;
  14.             if (i>=j)
  15.                 break;
  16.             exch(a, i, j);
  17.         }
  18.         exch(a, lo, j);
  19.         return j;
  20.     }
  22.     public static void sort(Comparable[] a){
  23.         StdRandom.shuffle(a);
  24.         sort(a, 0, a.length-1);
  25.     }
  26. }

Dijkstra 3-路划分快速排序

  1. /* Dijkstra 3-路划分快速排序 Quicksort with Dijkstra3-wayPartition */
  2. import edu.princeton.cs.algs4.StdRandom;
  3. public class QD3P {
  4.     public static void sort(Comparable[] a){
  5.         StdRandom.shuffle(a);
  6.         sort(a, 0, a.length-1);
  8.     }
  9.     private static void sort(Comparable[] a, int lo, int hi){
  10.         if (hi<=lo)
  11.             return;
  12.         int lt=lo, i=lo+1, gt=hi;
  13.         Comparable v=a[lo];
  14.         while (i<=gt){
  15.             int cmp=a[i].compareTo(v);
  16.             if (cmp<0)
  17.                 exch(a, lt++, i++);
  18.             else if (cmp>0)
  19.                 exch(a, i, gt--);
  20.             else 
  21.                 i++;
  22.         }
  23.         sort(a, lo, lt-1);
  24.         sort(a, gt+1, hi);
  25.     }
  26. }

测试

  1. import edu.princeton.cs.algs4.*;
  2. public class Test {
  3.     public static long t[] = new long[5];
  4.     public static double time(String alg, Double[] a){
  5.         long startns,  endns;
  6.         startns = System.nanoTime();
  7.         if (alg.equals("IS")) IS.sort(a);
  8.         else if (alg.equals("TDM")) TDM.sort(a);
  9.         else if (alg.equals("BUM")) BUM.sort(a);
  10.         else if (alg.equals("RQ")) RQ.sort(a);
  11.         else if (alg.equals("QD3P")) QD3P.sort(a);
  12.         endns = System.nanoTime();        
  13.         return (endns-startns)/1000;
  14.     }
  16.     public static void SORT(int i, String alg, int N, int T){
  17.         long time = 0;
  18.         Double[] a = new Double[N];
  19.         for (int t = 0; t < T; t++){
  20.             for (int j = 0; j < N; j++){
  21.                 a[j] = StdRandom.uniform();
  22.             }
  23.             time += time(alg, a);
  24.         }
  25.         t[i] = time / T;
  26.     }
  28.     public static void main(String[] args){
  29.         String alg[] = {"IS", "TDM", "BUM", "RQ", "QD3P"};
  30.         int N = 2000;
  31.         int T = 10;
  32.         for (int i=0; i<6; i++, N*=2){
  33.         System.out.println("N = " +N+", T = "+T);
  34.         System.out.println("\tRunning Time");
  35.         for (int j = 0; j < 5; j++){
  36.             SORT(j, alg[j], N, T);
  37.             System.out.print(alg[j]+"\t");
  38.             System.out.println(t[j]+"\tμs");
  39.         }
  40.         System.out.println();
  41.         }    
  42.   }
  43. }

N为排序的规模，T为运行次数

设N=2000，当N翻倍时，测试结果为

  1. N = 2000, T = 10
  2.     Running Time
  3. IS    4409    μs
  4. TDM    1299    μs
  5. BUM    1039    μs
  6. RQ    992    μs
  7. QD3P    963    μs
  9. N = 4000, T = 10
  10.     Running Time
  11. IS    10654    μs
  12. TDM    4556    μs
  13. BUM    6111    μs
  14. RQ    3777    μs
  15. QD3P    6086    μs
  17. N = 8000, T = 10
  18.     Running Time
  19. IS    41219    μs
  20. TDM    1835    μs
  21. BUM    1809    μs
  22. RQ    2542    μs
  23. QD3P    1935    μs
  25. N = 16000, T = 10
  26.     Running Time
  27. IS    180119    μs
  28. TDM    3760    μs
  29. BUM    3715    μs
  30. RQ    3122    μs
  31. QD3P    4094    μs
  33. N = 32000, T = 10
  34.     Running Time
  35. IS    810361    μs
  36. TDM    8284    μs
  37. BUM    8136    μs
  38. RQ    7053    μs
  39. QD3P    9210    μs
  41. N = 64000, T = 10
  42.     Running Time
  43. IS    3478466    μs
  44. TDM    17989    μs
  45. BUM    17470    μs
  46. RQ    15105    μs
  47. QD3P    20712    μs
五种排序算法比较






































算法 时间复杂度（平均） 空间复杂度 稳定性
IS O(N^2) O(1) 稳定
TDM O(NlogN) O(N) 稳定
BUM O(NlogN) O(N) 稳定
RQ O(NlogN)  O(NlogN) 不稳定
QD3P O(NlogN) O(NlogN) 不稳定

发表评论

表情：
评论列表 （有 0 条评论，309人围观）

还没有评论，来说两句吧...

相关阅读