06.归并排序

归并排序

1.基本思想
2.排序过程
3.代码实现
4.如何优化
5.复杂度
6.使用场景

1.基本思想

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

2.排序过程

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针到达序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
image

3.代码实现

代码如下所示

/**
 * 归并排序
 * 简介:将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，每个子序列是有序的。
 *     然后再把有序子序列合并为整体有序序列
 * 稳定排序方式
 * @param array 待排序数组
 * @return 输出有序数组
 */ 
public static int[] sort(int[] array, int low, int high) { 
    int mid = (low + high) / 2; 
    if (low < high) { 
        // 左边  
        sort(array, low, mid); 
        // 右边 
        sort(array, mid + 1, high); 
        // 左右归并  
        merge(array, low, mid, high); 
    }
    return array; 
} 

private static void merge(int[] array, int low, int mid, int high) {
    int[] temp = new int[high - low + 1]; 
    int i = low;
    // 左指针  
    int j = mid + 1;
    // 右指针  
    int k = 0; 
    // 把较小的数先移到新数组中  
    while (i <= mid && j <= high) { 
        if (array[i] < array[j]) { 
            temp[k++] = array[i++]; 
        } else { 
            temp[k++] = array[j++]; 
        } 
    } 
    // 把左边剩余的数移入数组  
    while (i <= mid) { 
        temp[k++] = array[i++]; 
    } 
    // 把右边边剩余的数移入数组  
    while (j <= high) { 
        temp[k++] = array[j++]; 
    } 
    // 把新数组中的数覆盖array数组  
    for (int k2 = 0; k2 < temp.length; k2++) { 
        array[k2 + low] = temp[k2]; 
    } 
}

第二种方式

@Override
public int[] sort(int[] sourceArray) throws Exception {
    // 对 arr 进行拷贝，不改变参数内容
    int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

    if (arr.length < 2) {
        return arr;
    }
    int middle = (int) Math.floor(arr.length / 2);

    int[] left = Arrays.copyOfRange(arr, 0, middle);
    int[] right = Arrays.copyOfRange(arr, middle, arr.length);

    return merge(sort(left), sort(right));
}

protected int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    int i = 0;
    while (left.length > 0 && right.length > 0) {
        if (left[0] <= right[0]) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        } else {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }
    }

    while (left.length > 0) {
        result[i++] = left[0];
        left = Arrays.copyOfRange(left, 1, left.length);
    }

    while (right.length > 0) {
        result[i++] = right[0];
        right = Arrays.copyOfRange(right, 1, right.length);
    }

    return result;
}

4.如何优化

5.复杂度

性能：时间复杂度总是为O(NlogN)，空间复杂度也总为为O(N)，算法与初始序列无关，排序是稳定的。