歸并排序

不斷地講無序數(shù)組分成兩部分比較

實現(xiàn):

import java.util.Arrays;


public class MergeSort {
    /**
     *
     * @param arr
     * @param l 數(shù)組最左邊的元素
     * @param mid 中間歸并的分隔
     * @param r 數(shù)組最右邊的元素
     */
//    如何歸并
    public static void merge(int[] arr,int l, int mid, int r){
        int[] aux = Arrays.copyOfRange(arr, l, r + 1);

//        設(shè)置兩個指針指向分開數(shù)組的頭尾
        int i = l,j = mid + 1;
        for (int k = l; k <= r; k++) {

            //左數(shù)組越界問題解決
            if (i > mid){
                arr[k] = aux[j-l];
                j++;
            }
            //右數(shù)組越界問題解決
            else if (j > r){
                arr[k] = aux[i-l];
                i++;
            }
            else if (aux[i-l] < aux[j-l]){
                arr[k] = aux[i-l];
                i++;
            }
            else{
                arr[k] = aux[j-l];
                j++;
            }
        }

    }

//    定義歸并的方法
//    將原來的數(shù)組進(jìn)行分割
    private static void sort(int[] arr,int l, int r){
        if (l >= r){
            return;
        }

        int mid = (l+r) / 2;

//        這里遞歸調(diào)用將數(shù)組分割到最小
        sort(arr, l, mid);
        sort(arr, mid+1, r);
//        分割后執(zhí)行遞歸
        merge(arr, l, mid, r);
    }

    public static void sort(int[] arr){

        int n = arr.length;
        sort(arr, 0, n-1);
    }

    public static void main(String[] args) {
        int[] arr = {5,8,1,4,3};
        MergeSort.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
    }
}

優(yōu)化在近乎有序數(shù)組時歸并排序的效率

private static void sort(int[] arr,int l,int r){

        if (l>=r){
            return;
        }

        int mid = (l+r)/2;
        sort(arr, l, r);
        sort(arr, mid + 1, r);
        if ( arr[mid] > arr[mid+1] ){
            merge(arr, l, mid, r);//優(yōu)化在近乎有序數(shù)組時用歸并排序時的效率
            //因為歸并排序左邊數(shù)組的最后一位元素小于右邊第一位的時候已經(jīng)確定了有序
        }

    }

歸并排序在于用空間換取時間，需要另外開辟新的數(shù)組空間來進(jìn)行歸并

快速排序

如何進(jìn)行取值分割（Partition）

實現(xiàn):

public class QuickSort {

    public static void sort(int[] arr){
        int n = arr.length;
        quickSort(arr, 0, n-1);
    }

    private static void quickSort(int[] arr,int l,int r){
        if (l >= r){
            return;
        }
        //其實也是j
        int p = partition(arr,l,r);
        quickSort(arr, l, p-1);
        quickSort(arr, p+1, r);
    }

    private static int partition(int[] arr, int l, int r) {
//        先取出一個比較數(shù)
        int v = arr[l];
//        l+1是開始排列的第一個元素
        int j = l;//表示大于v元素區(qū)域一開始為空
//        i是當(dāng)前訪問的元素
        for (int i = l+1; i < r ; i++) {
//            若i位置的元素小于v,則j會指向此區(qū)域
            if ( arr[i] < v){
//                與j+1位置的元素互換
//             第一種寫法：
                swap(arr,arr[j+1],arr[i]);
                j++;

//                第二種寫法:
//                swap(arr,arr[++j],arr[i]);
            }
        }
        swap(arr,arr[l],arr[j]);
        return j;
    }

    private static void swap(int[] arr, int i, int j) {

        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5,8,1,4,3};
        MergeSort.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
    }
}

為了避免當(dāng)數(shù)組近乎是有序或有大量重復(fù)時

雙路排序

實現(xiàn):

private static int partition(Comparable arr[],int l,int r){

        //選擇一個隨機數(shù)與第一個元素交換
        swap(arr, l, (int)(Math.random()*(r-l+1))+l);

        //拿出第一個元素做對比
        Comparable v = arr[l];

        //設(shè)i和j分別為左數(shù)組和右數(shù)組添加元素時指針
        int i = l+1,j=r;

        while (true){
            //若左數(shù)組下個元素小于v則考察下一個元素
            while(i<=r && arr[i].compareTo(v) <0){
                i++;
            }

            //若右數(shù)組下個元素大于v則考察下一個元素
            while(j<=l+1 && arr[j].compareTo(v) >0){
                j--;
            }
            //直到i>j時說明已經(jīng)考察到了所有元素
            if(i>j){
                break;
            }

            //當(dāng)兩個while循環(huán)都不滿足條件時
            //交換兩個數(shù)組的最后一個元素使之滿足v<i與v>j的條件
            swap(arr, i, j);
            i++;
            j--;
        }

        swap(arr, l, j);
        return j;
    }

三路排序

實現(xiàn):

    private static void partition(Comparable arr[],int l,int r){

        //選擇一個隨機數(shù)與第一個元素交換
        swap(arr, l, (int)(Math.random()*(r-l+1))+l);

        //拿出第一個元素做對比
        Comparable v = arr[l];

        int lt = l;     // arr[l+1...lt] < v 指向<v的最后一個元素
        int gt = r + 1; // arr[gt...r] > v
        int i = l+1;    // arr[lt+1...i) == v 作為考察元素指針

        //i<gt則說明元素還為考察到最后一個
        while (i < gt){
            if(arr[i].compareTo(v) < 0){
                swap(arr, i,lt+1);
                lt++;
                i++;
            }
            else if( arr[i].compareTo(v) > 0 ){
                swap( arr, i, gt-1);
                gt --;
            }
            else{ // arr[i] == v
                i ++;
            }
        }
        swap( arr, l, lt );

        sort(arr, l, lt-1);
        sort(arr, gt, r);
    }