概念

排序類的算法，有很強的實踐需求，是非?；A(chǔ)的一類算法。在找工作面試中，排序算法也是大概率出現(xiàn)。本文將講述排序常用的算法：歸并排序，快速排序和插入排序。

歸并排序

假如有一組亂序序列：a1, a2, a3 ... an，現(xiàn)在要將它從小到大的排序。

思想

1. 如果排序的序列長度為1，則返回
2. 將a1 ... an拆分為兩個序列： a1...an/2, an/2 +1 .... an
3. 遞歸對a1...an/2排序，遞歸對 an/2 +1 .... an排序
4. 合并3步的兩個有序序列的結(jié)果

案列

待排序列：1, 23, 3, 4, 8, 9，7
拆分歸并如下圖?？梢钥吹剑喈?dāng)于樹從下往上處理。

拆分歸并圖

代碼

···

public void testMergeSort() {
    int[] from = {1, 23, 3, 4, 8, 9, 7};
    mergeSort(from, 0, from.length - 1);
    Arrays.stream(from).forEach(System.out :: println);
}


public void mergeSort(int[] from, int start, int end) {
    if (start >= end) {
        return;
    }

    int mid = (end + start) / 2;
    mergeSort(from, start, mid);
    mergeSort(from, mid + 1, end);
    merge(from, start, mid, end);
}

/**
 *
 *
 * @param from
 * @param low the begin position for from and to
 * @param mid the mergeFrom1 end position
 * @param high the merge from2 end position
 */
public void merge(int[] from, final int low, final int mid, final int high) {
    int firstPosition = low;
    int firstEndPosition = mid;
    int secondPosition = mid + 1;
    int secondEndPosition = high;

    int length = high - low + 1;
    int[] to = new int[high - low + 1];
    int i = 0;

    while (i <= length - 1) {
        if (firstPosition <= firstEndPosition && secondPosition <= secondEndPosition) {
            if (from[firstPosition] > (from[secondPosition])) {
                to[i ++] = from[secondPosition ++];
            } else {
                to[i ++] = from[firstPosition ++];
            }
        } else if (firstPosition <= firstEndPosition) {
            to[i ++] = from[firstPosition ++];
        } else if (secondPosition <= secondEndPosition) {
            to[i ++] = from[secondPosition];
        }
    }
    System.arraycopy(to, 0, from, low, length);
}

···