1. 歸并排序算法的使用情景

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

2. 自頂向下的歸并排序

自頂向下的排序算法就是把數(shù)組元素不斷的二分，直到子數(shù)組的元素個(gè)數(shù)為一個(gè)，因?yàn)檫@個(gè)時(shí)候子數(shù)組必定是已有序的，然后將兩個(gè)有序的序列合并成一個(gè)新的有序的序列，兩個(gè)新的有序序列又可以合并成另一個(gè)新的有序序列，以此類推，直到合并成一個(gè)有序的數(shù)組。

平面設(shè)計(jì)培訓(xùn),網(wǎng)頁設(shè)計(jì)培訓(xùn),美工培訓(xùn),游戲開發(fā),動(dòng)畫培訓(xùn)

為了體現(xiàn)歸并的排序的穩(wěn)定性，我們的代碼使用java的泛型來實(shí)現(xiàn)對任意對象的排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static <T extends Comparable<? super T>>
void MergeSortUpToDown(T[] A){
    @SuppressWarnings("unchecked")
    //創(chuàng)建合并兩個(gè)有序序列的輔助數(shù)組
    T[] aux = (T[])Array.newInstance(A.getClass().getComponentType(), A.length);
    mergeSortUpToDown0(A, aux, 0, A.length-1);
}
 
public static <T extends Comparable<? super T>>
void mergeSortUpToDown0(T[] A, T[] aux, int start, int end){
    if(start == end)
        return;
    int mid = (start+end)/2;
    mergeSortUpToDown0(A, aux, start, mid);
    mergeSortUpToDown0(A, aux, mid+1, end);
    //復(fù)制到輔助數(shù)組中,此時(shí)[start,mid] [mid+1, end]兩個(gè)子數(shù)組已經(jīng)有序
    System.arraycopy(A, start, aux, start, end - start + 1);
    //然后歸并回來
    int i = start, j = mid+1, k;
    for(k = start; k <= end; k++){
        if(i > mid){
            A[k] = aux[j++];
        }else
        if(j > end){
            A[k] = aux[i++];
        }else
        if(aux[i].compareTo(aux[j]) <= 0){
            A[k] = aux[i++];
        }else{
            A[k] = aux[j++];
        }
    }
}

3. 自底向上的歸并排序

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

平面設(shè)計(jì)培訓(xùn),網(wǎng)頁設(shè)計(jì)培訓(xùn),美工培訓(xùn),游戲開發(fā),動(dòng)畫培訓(xùn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//自底向上歸并排序
public static <T extends Comparable<? super T>> void MergeSortDownToUp(T[] A){
    @SuppressWarnings("unchecked")
    T[] aux = (T[])Array.newInstance(A.getClass().getComponentType(), A.length);
    int len,i,j,k,start,mid,end;
    //len表示歸并子數(shù)組的長度，1表示，一個(gè)一個(gè)的歸并，歸并后的長度為2,2表示兩個(gè)兩個(gè)的歸并，歸并后的長度為4,以此類推
    for(len = 1; len < A.length; len = 2*len){
        //復(fù)制到輔助數(shù)組中
        System.arraycopy(A, 0, aux, 0, A.length);
        //按照len的長度歸并回A數(shù)組，歸并后長度翻倍
        for(start = 0; start < A.length; start = start+2*len){
            mid = start + len - 1;
            //對于數(shù)組長度不滿足2的x次冪的數(shù)組，mid可能會(huì)大于end
            end = Math.min(start + 2*len - 1, A.length-1);
            i = start;
            //mid大于end時(shí),j必然大于end,所以不會(huì)引起越界訪問
            j = mid+1;
            //[start,mid] [mid+1, end]
            for(k = start; k <= end; k++){
                if(i > mid){
                    A[k] = aux[j++];
                }else
                if(j > end){
                    A[k] = aux[i++];
                }else
                if(aux[i].compareTo(aux[j]) < 0){
                    A[k] = aux[i++];
                }else{
                    A[k] = aux[j++];
                }
            }
        }
    }
}

4. 參考文章

[1] 算法（第四版）RobertSedgewick

分類: 算法