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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70][]

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

整个过程需要以下API：

/* 返回 v<w */
    private static boolean less(Comparable v, Comparable w){
    		return v.compareTo(w)<0;
    	}
    
    /* 交换a[i]与a[j]的位置 */
    private static void exch(Comparable[] a, int i, int j){
    		Comparable temp = a[i];
    		a[i] = a[j];
    		a[j] = temp;
    	}

插入排序：

/* 插入排序 InsertSort */
    public class IS {
    	private static long S = 0;
    	public static void sort(Double[] a){
    		int N = a.length;
    		for (int i = 1; i < N; i++){
    			for (int j = i; j > 0 && less(a[j], a[j-1]); j--){
    				exch(a, j, j-1);
    			}
    		}
    	}
    }

自顶向下归并排序：

/* 自顶向下归并排序 Top-DownMergeSort */
    public class TDM {
    	private static Comparable[] aux;
    	public static void merge(Comparable[] a, int lo, int mid, int hi){
    		int i=lo, j=mid+1;
    		for (int k=lo; k<=hi; k++)
    			aux[k]=a[k];
    		
    		for (int k=lo; k<=hi; k++){
    			if (i>mid)
    				a[k]=aux[j++];
    			else if (j>hi)
    				a[k]=aux[i++];
    			else if (less(aux[j], aux[i]))
    				a[k]=aux[j++];
    			else 
    				a[k]=aux[i++];
    		}
    	}
    	
    	public static void sort(Comparable[] a){
    		aux=new Comparable[a.length];
    		sort(a, 0, a.length-1);
    	}
    	
    	private static void sort(Comparable[] a, int lo, int hi){
    		if (hi<=lo)
    			return;
    		int mid=lo+(hi-lo)/2;
    		sort(a, lo, mid);
    		sort(a, mid+1, hi);
    		merge(a, lo, mid, hi);
    	}	
    }

自底向上归并排序

/* 自底向上归并排序 Bottom-UpMergeSort */
    public class BUM {
    	private static Comparable[] aux;
    	public static void merge(Comparable[] a, int lo, int mid, int hi){
    		int i=lo, j=mid+1;
    		for (int k=lo; k<=hi; k++)
    			aux[k]=a[k];
    		
    		for (int k=lo; k<=hi; k++){
    			if (i>mid)
    				a[k]=aux[j++];
    			else if (j>hi)
    				a[k]=aux[i++];
    			else if (less(aux[j], aux[i]))
    				a[k]=aux[j++];
    			else 
    				a[k]=aux[i++];
    		}
    	}
    	
    	public static void sort(Comparable[] a){
    		int N=a.length;
    		aux=new Comparable[N];
    		for (int sz=1; sz<N; sz=sz+sz)
    			for (int lo=0; lo<N-sz; lo+=sz+sz)
    				merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
    	}
    }

随机快速排序

/* 随机快速排序 RandomQuickSort */
    import edu.princeton.cs.algs4.StdRandom;
    public class RQ {
    	private static int partition(Comparable[] a, int lo, int hi){
    		int i=lo, j=hi+1;
    		while (true){
    			while (less(a[++i],a[lo]))
    				if (i==hi)
    					break;
    			while (less(a[lo], a[--j]))
    				if (j==lo)
    					break;
    			
    			if (i>=j)
    				break;
    			exch(a, i, j);
    		}
    		exch(a, lo, j);
    		return j;
    	}
    	
    	public static void sort(Comparable[] a){
    		StdRandom.shuffle(a);
    		sort(a, 0, a.length-1);
    	}
    }

Dijkstra 3-路划分快速排序

/* Dijkstra 3-路划分快速排序 Quicksort with Dijkstra3-wayPartition */
    import edu.princeton.cs.algs4.StdRandom;
    public class QD3P {
    	public static void sort(Comparable[] a){
    		StdRandom.shuffle(a);
    		sort(a, 0, a.length-1);
    
    	}
    	private static void sort(Comparable[] a, int lo, int hi){
    		if (hi<=lo)
    			return;
    		int lt=lo, i=lo+1, gt=hi;
    		Comparable v=a[lo];
    		while (i<=gt){
    			int cmp=a[i].compareTo(v);
    			if (cmp<0)
    				exch(a, lt++, i++);
    			else if (cmp>0)
    				exch(a, i, gt--);
    			else 
    				i++;
    		}
    		sort(a, lo, lt-1);
    		sort(a, gt+1, hi);
    	}
    }

测试

import edu.princeton.cs.algs4.*;
    public class Test {
    	public static long t[] = new long[5];
    	public static double time(String alg, Double[] a){
    		long startns,  endns;
    		startns = System.nanoTime();
    		if (alg.equals("IS")) IS.sort(a);
    		else if (alg.equals("TDM")) TDM.sort(a);
    		else if (alg.equals("BUM")) BUM.sort(a);
    		else if (alg.equals("RQ")) RQ.sort(a);
    		else if (alg.equals("QD3P")) QD3P.sort(a);
    		endns = System.nanoTime();		
    		return (endns-startns)/1000;
    	}
    	
    	public static void SORT(int i, String alg, int N, int T){
    		long time = 0;
    		Double[] a = new Double[N];
    		for (int t = 0; t < T; t++){
    			for (int j = 0; j < N; j++){
    				a[j] = StdRandom.uniform();
    			}
    			time += time(alg, a);
    		}
    		t[i] = time / T;
    	}
    	
    	public static void main(String[] args){
    		String alg[] = {"IS", "TDM", "BUM", "RQ", "QD3P"};
    		int N = 2000;
    		int T = 10;
    		for (int i=0; i<6; i++, N*=2){
    		System.out.println("N = " +N+", T = "+T);
    		System.out.println("\tRunning Time");
    		for (int j = 0; j < 5; j++){
    			SORT(j, alg[j], N, T);
    			System.out.print(alg[j]+"\t");
    			System.out.println(t[j]+"\tμs");
    		}
    		System.out.println();
    		}	
      }
    }

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

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

N = 2000, T = 10
    	Running Time
    IS	4409	μs
    TDM	1299	μs
    BUM	1039	μs
    RQ	992	μs
    QD3P	963	μs
    
    N = 4000, T = 10
    	Running Time
    IS	10654	μs
    TDM	4556	μs
    BUM	6111	μs
    RQ	3777	μs
    QD3P	6086	μs
    
    N = 8000, T = 10
    	Running Time
    IS	41219	μs
    TDM	1835	μs
    BUM	1809	μs
    RQ	2542	μs
    QD3P	1935	μs
    
    N = 16000, T = 10
    	Running Time
    IS	180119	μs
    TDM	3760	μs
    BUM	3715	μs
    RQ	3122	μs
    QD3P	4094	μs
    
    N = 32000, T = 10
    	Running Time
    IS	810361	μs
    TDM	8284	μs
    BUM	8136	μs
    RQ	7053	μs
    QD3P	9210	μs
    
    N = 64000, T = 10
    	Running Time
    IS	3478466	μs
    TDM	17989	μs
    BUM	17470	μs
    RQ	15105	μs
    QD3P	20712	μs

<table style="width:500px;">  五种排序算法比较  
 <tbody> 
  <tr> 
   <td>算法</td> 
   <td>时间复杂度（平均）</td> 
   <td>空间复杂度</td> 
   <td>稳定性</td> 
  </tr> 
  <tr> 
   <td>IS</td> 
   <td>O(N^2)</td> 
   <td>O(1)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>TDM</td> 
   <td>O(N*logN)</td> 
   <td>O(N)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>BUM</td> 
   <td>O(N*logN)</td> 
   <td>O(N)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>RQ</td> 
   <td>O(N*logN)&nbsp;</td> 
   <td>O(N*logN)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>QD3P</td> 
   <td>O(N*logN)</td> 
   <td>O(N*logN)</td> 
   <td>不稳定</td> 
  </tr> 
 </tbody> 
</table>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RYSDkyNA_size_16_color_FFFFFF_t_70]: /images/20220415/c8111760dabb44ecb44b1e36cfa78a92.png