歸并排序算法和快速排序算法是java.util.Arrays中使用的排序算。對(duì)于一般的基本數(shù)據(jù)類(lèi)型，Arrays.sort函數(shù)使用雙軸快速排序算法，而對(duì)于對(duì)象類(lèi)型使用歸并排序（準(zhǔn)確的說(shuō)使用的是TimSort排序算法，它是歸并排序的優(yōu)化版本）。這樣做的原因有兩點(diǎn)，第一個(gè)原因，歸并排序是穩(wěn)定的，而快速排序不是穩(wěn)定的。第二個(gè)原因，對(duì)于基本數(shù)據(jù)類(lèi)型，排序的穩(wěn)定性意義不大，但對(duì)于復(fù)合數(shù)據(jù)類(lèi)型（比如對(duì)象）排序的穩(wěn)定性就能幫助我們保持排序結(jié)果的某些性質(zhì)。
j

• 自底向上排序
  自底向上的歸并排序算法的思想就是數(shù)組中先一個(gè)一個(gè)歸并成兩兩有序的序列，兩兩有序的序列歸并成四個(gè)四個(gè)有序的序列，然后四個(gè)四個(gè)有序的序列歸并八個(gè)八個(gè)有序的序列，以此類(lèi)推，直到，歸并的長(zhǎng)度大于整個(gè)數(shù)組的長(zhǎng)度，此時(shí)整個(gè)數(shù)組有序。需要注意的是數(shù)組按照歸并長(zhǎng)度劃分，最后一個(gè)子數(shù)組可能不滿(mǎn)足長(zhǎng)度要求，這個(gè)情況需要特殊處理。自頂下下的歸并排序算法一般用遞歸來(lái)實(shí)現(xiàn)，而自底向上可以用循環(huán)來(lái)實(shí)現(xiàn)。

1.png

    public void mergeSort(int[] a){
        int len = 1;
        while(len < a.length){
            for(int i = 0; i < a.length; i += 2*len){
                merge(a, i, len);
            }
            len *= 2;
        }
    }

    public void merge(int[] a, int i, int len){
        int start = i;
        int len_i = i + len;//歸并的前半部分?jǐn)?shù)組[0,1)
        int j = i + len;
        int len_j = j +len;//歸并的后半部分?jǐn)?shù)組[1,2)
        int[] temp = new int[2*len];
        int count = 0;
        while(i < len_i && j < len_j && j < a.length){
            if(a[i] <= a[j]){
                temp[count++] = a[i++];
            }
            else{
                temp[count++] = a[j++];
            }
        }
        while(i < len_i && i < a.length){//注意：這里i也有可能超過(guò)數(shù)組長(zhǎng)度
            temp[count++] = a[i++];
        }
        while(j < len_j && j < a.length){
            temp[count++] = a[j++];
        }
        count = 0;
        while(start < j && start < a.length){
            a[start++] = temp[count++];
        }
    }

• 自頂向下

2.jpg

    private static void mergeSort(int[] arr, int left, int right) {
        if (left<right) {
            int middle=(left+right)/2;
            mergeSort(arr, left, middle);
            mergeSort(arr, middle+1, right);
            merge(arr,left,middle,right);
        }
    }

    private static void merge(int[] arr, int left, int middle, int right) {
        int [] tempArray=new int[arr.length];
        int rightStart=middle+1;
        int temp=left;
        int third=left;
        while(left<=middle&&rightStart<=right){
            if (arr[left]<=arr[rightStart]) {
                tempArray[third]=arr[left];
                third++;
                left++;
            }else {
                tempArray[third]=arr[rightStart];
                third++;
                rightStart++;
            }
        }
        while(left<=middle){
            tempArray[third]=arr[left];
            third++;
            left++;
        }
        while (rightStart<=right) {
            tempArray[third]=arr[rightStart];
            third++;
            rightStart++;
        }
        while (temp<=right) {
            arr[temp]=tempArray[temp];
            temp++;
        }
    }