这是一篇自学文章,如果有错误地方请及时指出

归并排序

• 就是将多个有序数组合并成一个有序数组,那么多个有序数组是由一个无序数组拆分比较在排序产生的,如果参与合并的只有两个有序表,那么就称为二路合并.本文是以二路合并开始学习的,当然也有多路合并

归并流程

• 直接上图

• 当然下面两个还没有合并成整个的有序数组,因为画不下了...

比较原理

代码实现

import java.util.Arrays;

public class SSS {
    public static void main(String[] args) {
        int[] arr = {2,5,4,7,8,3,1,9,0};
        mergeSort(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr, int start, int end) {
        //代表已经拆分到不可再拆了
        if (start>=end){
            return;
        }
        int middle = (start + end) / 2;
        mergeSort(arr,start,middle);
        mergeSort(arr,middle+1,end);
        merge(arr,start,middle,end);
    }

    private static void merge(int[] arr, int start, int middle, int end) {
        //临时数组的下标索引
        int index = 0;
        int[] tempArr = new int[end - start + 1];
        int s = start;
        int se = middle;
        int m = middle +1;
        int me = end;
        //s<=se即第一个待排序数组,m<=me即第二个待排序数组,可以看代码变量说明图
        while (s<=se && m<=me){
            //即第一个待排序数组和第二个待排序数组开始比较
            if (arr[s] < arr[m]){
                //如果s比较小,那么就赋值给临时数组,然后将s边的数组索引往后移一位
                tempArr[index++] = arr[s++];
            }else {
                //到这就算m边比较小了,那么就赋值给临时数组,然后将m边的数组索引往后移一位
                tempArr[index++] = arr[m++];
            }
        }
        //下面这两个循环,代表如果切分的不是五五开,比如一边有4个元素一边有3个元素,然而上面的循环只能是比较
        //两边元素的前三个,而会有一个剩余的没有添加进来,所以下面循环是来判断不是五五开的情况的
        while (s<=se){
            tempArr[index++] = arr[s++];
        }
        while (m<=me){
            tempArr[index++] = arr[m++];
        }
        //到这了,那么这次的两个待排序数组就已经排序完毕,已经放入tempArr里面了.
        //我们的方法的参数start代表了这次数组比较的开始,所以我们还必须将整个tempArr里面的元素
        //倒入进arr里,开始就是start位置
        for (int i = 0; i < index; i++) {
            arr[start+i] = tempArr[i];
        }
    }
}