归并排序

个人主页：https://chengang.plus/

文章将会同步到个人微信公众号：Android部落格

1.1 描述

归并排序不断缩小比较范围，每次分为两部分，首先从数组中间分成两边比较，再分别将两边再分割成两部分，直到每个部分为2个元素。

这两个元素比较完成之后，再合并；合并之后再与其他合并部分做比较，再合并，以此循环。

先分开，比较之后在合并成一个整体。最后整体有序。

1.2 代码

static int[] numbers = {5,4,3,7,2,5,1,9,12,6,8,1,34};
public static void merge(int[] array,int left,int right){
    if(left < right){
        int middle = (left + right) / 2;
        merge(array,left ,middle);
        merge(array,middle + 1,right);
        sort(array,left,middle,right);
    }
}

public static void sort(int[] array,int left,int middle,int right){
    int i = left;
    int j = middle + 1;
    int temp = 0;
    while(i <= middle && j <= right){
        if(numbers[i] > numbers[j]){
            array[temp++] = numbers[j++];
        }else {
            array[temp++] = numbers[i++];
        }
    }
    while(i <= middle){
        array[temp++] = numbers[i++];
    }
    while(j <= right){
        array[temp++] = numbers[j++];
    }
    for(int value:array){
        System.out.println("mergeSort array value is:" + value);
    }
    System.out.println("-----------------");
    temp = 0;
    while(left <= right){
        numbers[left++] = array[temp++];
    }
}

public static void mergeSort(){
    int size = numbers.length;
    int[] curArray = new int[size];
    merge(curArray,0,size - 1);
    for(int value:numbers){
        System.out.println("mergeSort value is:" + value);
    }
}

public static void main(String[] args) {
    mergeSort();
}

1.3 总结

• merge

通过不断递归调用merge方法，确定left，middle，right的值，然后以middle为界，不断递归确定元素的比较范围。

• sort

将左右范围的元素按照各自的起始序号逐个比较，较小的元素排在前面，较大元素排在后面。

不断加大左右比较范围，然后重复上一步的比较。

sort其实是一个并的过程。

图片来自https://www.cnblogs.com/chengxiao/p/6194356.html

归并排序.png