归并排序--学习

归并排序

思路

1、尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素是1为止。

2、将相邻的两个子组进行合并成一个有序的大组。

3、不断的重复步骤2，直到最终只有一个组为止。

·········· 图片上面为分，下面为合

流程

数字代表顺序

代码

public class MergeSort {
    public static void main(String[] args) {
        int[] value = {8, 4, 5, 7, 1, 3, 6, 2};
        new MergeSort().sort(value);
        for (int item : value) {
            System.out.print(item + ",");
        }
    }


    public void sort(int[] value){
        int left = 0;
        int right = value.length - 1;
        int[] temp = new int[value.length];
        this.mergeSort(value, left, right, temp);
    }


    //分+合
    public void mergeSort(int[] value, int left, int right, int[] temp){
        if (left < right){
            int mid = (left + right) / 2;
            mergeSort(value, left, mid, temp);		//------>向左分
            mergeSort(value, mid + 1, right, temp);	//------>向右分
            merge(value, left, mid, right, temp);	//------>调用合并的方法
        }
    }

    //合并
    public void merge(int[] value, int left, int mid, int right, int[] temp){
        int i = left;      
        int j = mid + 1;     
        int t = 0;          

        while (i <= mid && j <= right){
            if (value[i] <= value[j]){
                temp[t] = value[i];
                t = t + 1;
                i = i + 1;
            } else {
                temp[t] = value[j];
                t += 1;
                j += 1;
            }
        }

        while( i <= mid) {
            temp[t] = value[i];
            t += 1;
            i += 1;
        }

        while( j <= right) {
            temp[t] = value[j];
            t += 1;
            j += 1;
        }

        t = 0;
        int tempLeft = left; 
        while(tempLeft <= right) {
            value[tempLeft] = temp[t];
            t += 1;
            tempLeft += 1;
        }
    }
}