【排序算法】归并排序

1  前言

今天把排序的几个算法过一下，这节我们看一下归并排序，简单的来说就是先拆再合，跟快排相反（快排时先找位置再两边拆），我们看示例。

2  代码示例

/**
 * 归并排序
 * 特点就是 跟快排相反，快排是先找再拆分，归并是先拆再合
 * 折半拆，指导拆分单个以后开始向上汇集
 */
public static void mergeSort(int[] arr, int[] res, int start, int end) {
    // 递归的出口，元素只有一个的时候直接返回
    if (start >= end) {
        return;
    }
    // 计算中间索引位置
    int middle = start + (end - start) / 2;
    // 拆分成两半，左边就是 0 ~ middle 右边就是 middle+1 ~ end
    int rightStart = middle + 1;
    // 左侧进行递归
    mergeSort(arr, res, start, middle);
    // 右侧进行递归
    mergeSort(arr, res,rightStart, end);
    // 开始汇集结果
    // 左侧索引变量
    int leftIndex = start;
    // 右侧索引变量
    int rightIndex = rightStart;
    // 结果的索引变量
    int index = start;
    // 左右两侧的数据都未汇集结束时
    while (leftIndex <= middle && rightIndex <= end) {
        // 升序，当左侧的值小于右侧的话，收集左侧的并将索引++
        if (arr[leftIndex] < arr[rightIndex]) {
            res[index++] = arr[leftIndex++];
            continue;
        }
        // 右侧的值小于左侧的，收集右侧的并将索引++
        res[index++] = arr[rightIndex++];
    }
    // 左侧的未处理干净时，收集剩余的
    while (leftIndex <= middle) {
        res[index++] = arr[leftIndex++];
    }
    // 右侧的未处理干净时，收集剩余的
    while (rightIndex <= end) {
        res[index++] = arr[rightIndex++];
    }
    /**
     * 这个是将排序后的顺序进行回写
     * 为什么要回写呢？因为后一次的结果汇集依赖前一次的结果
     *
     * 为什么要多个参数 res？
     * 这个我们在中间做拆分进行部分结果排序的时候不能直接在源数组上变更，所以需要个数据来存放排完序后覆盖回去
     */
    for (int i=start; i <= end; i++) {
        arr[i] = res[i];
    }
}
public static void main(String[] args) {
    int[] arr = IntStream.generate(() -> ThreadLocalRandom.current().nextInt(10000)).limit(10000).toArray();
    System.out.println("排序前：" + Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining(",")));
    int[] res = new int[arr.length];
    mergeSort(arr, res, 0, arr.length - 1);
    System.out.println("排序后：" + Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining(",")));
}

3  小结

有写的不对的地方，欢迎指正哈。