归并排序 merge sort 2018-06-26

先将一个序列分成很多个不能再分割的子序列，将各个子序列分别排序后再将子序列合并。其实就是重复两个步骤：【1】分【2】合并。
首先是第一个小问题，怎么分?
比如说一个序列:12 ,23,1,44,233,10,9,8。我们先分成两段：12 ,23,1,44 和 233,10,9,8，
发现还能再分成4段：12 ,23 和 1,44------233,10 和 9,8。
再分成8段：12--23--1--44 和233--10--9--8。
这时候开始把子序列进行排序合并，一个元素就是有序的。所以不用排序。
合并成2个一组排序得到：12，23----1，44---10，233---8，9。
再合并成4个一组排序得到：1，12，23，44---8，9，10，233。
最后合并得到最终结果：1，8，9，10，12，23，44，233。

public void mergeSort(int a[], int start, int end, int temp[]) {//分段
        if (start < end) {
            int mid = (start + end) / 2;
            mergeSort(a, start, mid, temp);
            mergeSort(a, mid + 1, end, temp);
            mergeArray(a, start, mid, end, temp);
            System.out.println(mid);
        }
    }

    /**
     * @param a
     * @param start
     * @param mid
     * @param end
     * @param temp
     *            <p>
     *            Description:合并
     *            </p>
     */
    private void mergeArray(int[] a, int start, int mid, int end, int[] temp) {
        int m = mid;
        int n = end;
        int i = start;
        int j = mid + 1;
        int k = 0;
        while (i <= m && j <= n) {
            if (a[i] < a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }
        while (i <= m) {
            temp[k++] = a[i++];
        }
        while (j <= n) {
            temp[k++] = a[j++];
        }
        for (int h = 0; h < k; h++) {
            a[start + h] = temp[h];
        }
    }

public void mergeSort(int[] a, int left, int right){
if(left < right){
int mid = (left + right)/2;
mergeSort(a, left, mid);
mergeSort(a, mid+1, right);
merge(a,left, mid, right);
}
}

/**
 * a[left]-a[mid] 和 a[mid+1],a[right]做合并
 * @param a
 * @param left
 * @param mid
 * @param right
 */
private void merge(int[] a, int left, int mid, int right) {
    int i = left;
    int j = mid +1;
    int k = 0;
    int[] temp = new int[right - left + 1];
    while(i<=mid && j <=right){
        if(a[i]<a[j]){
            temp[k++] = a[i++];
        }else {
            temp[k++] = a[j++];
        }
    }
    while (i<=mid){
        temp[k++]= a[i++];
    }
    while(j<=right){
        temp[k++]= a[j++];
    }

    for(int h =0 ; h<k; h++){
        a[left + h] = temp[h];
    }
}