歸并排序：

image.png

歸并所用到的思想是分治思想，何為分治，就是分而治之，大問題分解為小問題，讓后把小問題的解合并在一起就是大問題的答案，歸并可以理解為遞歸和合并，歸并排序是穩(wěn)定的，但是不是原地排序。

時間復雜度：

O（nlogn）

空間復雜度：

O（n）
原因是每次合并所用到的額外空間都會釋放，而不是累加

歸并排序的實現

利用遞歸
1、遞歸的終止條件為
p >= r （p、r分別為分解后的區(qū)域的頭尾下標）
2、遞歸公式：
mergeSort(p....r) = mergeSort(p...q),mergeSort(p+1....r)

 public void mergeSort(int[] a){
        mergeSort(a,0,a.length-1);
    }

    private static  void mergeSort(int[] a , int p,int r){
        //終止條件
        if (p >= r){
            return;
        }

        //遞歸
        int q = (p+r)/2;
        mergeSort(a,p,q);
        mergeSort(a,q+1,r);

        merge(a , p ,r,q); //合并


    }

merge() 合并方法

 //合并函數（無哨兵版）
    private static void merge(int[] a, int p, int r,int q) {
        int i = p ; int j = q+1; int k = 0;

        int[] tmp = new int[r-p+1];
        while (i <= q && j <= r){
            if (a[i] <= a[j]){
                tmp[k++] = a[i++];
            }
            else {
                tmp[k++] = a[j++];
            }
        }

        int start = i;
        int end = q;
        if (j <= r){
            start = j;
            end = r;
        }
        //將剩余的元素拷貝到臨時數組
        while (start <= end){
            tmp[k++] = a[start++];
        }

        //將tmp拷貝回原數組
        for (int n = 0 ; n < tmp.length;n++){
            a[p+n] = tmp[n];
        }
    }

添加了哨兵

  //合并函數哨兵版
    private static void merge2(int[] a, int p ,int r,int q){
        int i = p ; int j = q+1 ; int k = p;
        //將要合并的兩個部分分別放入兩個數組中
        int[] r1 = new int[q-p+2];
        int[] r2 = new int[r-q+1];

        for (int n=0;n+i <= q ; n++){
            r1[n] = a[n+i];
        }
        r1[r1.length-1] = Integer.MAX_VALUE;//在數組后面加個最大值 即添加哨兵

        for (int n=0;n+j <= r ; n++){
            r2[n] = a[n+j];
        }
        r2[r2.length-1] = Integer.MAX_VALUE;
        //之后就無需判斷哪個數組沒有清空，直接清空完兩個臨時數組
        for (k = p ,i = 0 ,j = 0; k <=r ;k++){
            if (r1[i] < r2[j]){
                a[k] = r1[i];
                i++;
            }
            else {
                a[k] = r2[j];
                j++;
            }
        }


    }

快速排序：

不穩(wěn)定、原地排序

時間復雜度：

O(nlogn) 平均
O(n^2) 最壞

先進行分區(qū)，然后再處理子問題。先以數組最后一個元素作為分區(qū)點，將大于分區(qū)點的元素放在分區(qū)點右邊，反之放左邊。

例如：

8 10 2 3 6 1 5

選取 5

分區(qū)后

2 3 1 5 8 10 6

繼續(xù)對兩個區(qū)域進行快速排序，直到不可分解為止 即（p>=r）

 //快速排序
    public void  quickSort(int[] a){
        quickSort(a , 0 , a.length-1);

    }

    private void quickSort(int[] a, int p, int r) {

        //遞歸終止條件
        if (p >= r) return;

        //分區(qū) 返回分開兩個部分的下標 ，左邊的都比q小，右邊都比q大
       int q = partition( a, p,  r);

        //遞歸
        quickSort(a , p , q-1);
        quickSort(a , q+1 ,r);


    }

為了使排序是原地的，通過交換元素解決。

  //分區(qū)函數
    private static int partition(int[] a, int p, int r) {
        int pivot = a[r];//以所傳入的區(qū)域的最右邊的元素作為分區(qū)點
        int i=p ;
        for (int j = p ; j <= r-1 ; j++){
            if (a[j] < pivot){
                swap(a,j,i);//交換j、i
                i++;
            }

        }
        swap(a,i,r);//所有的元素都處理過了（處理的區(qū)域為【p，r-1】)，讓分區(qū)點換到自己的真正的位置
        return i;//返回分區(qū)點下標
    }

    private static void swap(int[] a, int b ,int c){
        int temp = a[b];
        a[b] = a[c];
        a[c] = temp;
    }