归并排序

归并排序采用递归分治的方式来实现排序。

1. 将原数组分为左、右两个数组；

2. 分别对左、右两个数组进行排序；

3. 将排序完毕的左、右数组，根据排序规则合并成一个数组。

归并排序

/**
 * 递归的将数组拆分成左右两个排序好的数组，再合并两个数组
 * @param array
 * @param left
 * @param right
 */
public void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        int center = (right + left) / 2;
        mergeSort(array, left, center);
        mergeSort(array, center + 1, right);
        merge(array, left, center, right);
    }
    return;
}

private void merge(int[] array, int left,int center, int right) {
    int[] temp = new int[right - left + 1];
    int li = left;
    int ri = center + 1;
    for (int i = 0; i < temp.length; i++) {
        if (li < center + 1 && ri < right + 1) {
            if (array[li] < array[ri]) {
                temp[i] = array[li++];
            } else {
                temp[i] = array[ri++];
            }
        } else {
            if (li > center) {  // 左侧的数组已经没有元素了，则将右侧的剩余元素加入temp
                temp[i] = array[ri++];
            } else {            // 反之，将左侧的剩余元素加入temp
                temp[i] = array[li++];
            }
        }
    }
    // 将temp中的元素加入array
    addAll(array, temp, left);
}

private void addAll(int[] array, int[] temp, int start) {
    for (int i = 0; i < temp.length; i++) {
        array[start++] = temp[i];
    }
}