归并排序

归并排序

public static void merge(int[] arr,int L,int R,int M) {
		//左右两边数组长度
        int left_size = M - L;
        int right_size = R - M + 1;
		
		//分为两个数组        
        int[] left = new int[left_size];
        int[] right = new int[right_size];
        
		//分别放入自己设好的数组里边，注意i的取值范围，应与L，R挂钩
        for(int i = L; i < M;i++) {
            left[i - L] = arr[i];
        }
        for(int i = M; i <= R;i++) {
            right[i - M] = arr[i];
        }


        int i = 0;
        int j = 0;
        int k = L;
        //开始比较大小，小的放前面
        while(i < left_size && j < right_size) {
            if(left[i] < right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }
        //如果一边数组已经到底了，另一边数组讲剩下的数据放入
        while(i < left_size) {
            arr[k++] = left[i++];
        }
        while (j < right_size) {
            arr[k++] = right[j++];
        }
    }

public static void mergesort(int[] arr , int L ,int R) {
		//如果L == R停止
        if(L == R) {
            return;
        } else  {
            int M = (R + L) / 2;
            //对左边进行归并
            mergesort(arr,L,M);
            //对右边进行归并
            mergesort(arr,M + 1,R);
            //排序
            merge(arr,L,R,M + 1);
        }
    }

我们要清楚的是，归并这个方法实质上使用的是分治的思想，便是把数组分成很多组，利用递归，递归到两个两个一组，从这开始比较，merge方法的使用前提就是两个数组是有序的，不然无法比较，所以递归到两个两个一组的时候，对一组开始排序，因为两个数字分为两个数组，一定是排好序的，那么就满足merge排序的前提，可以开始排序，以此递推，到整个数组分为两半时，两边的两个数组一定是有序的，最后再进行一次排序，就得到答案了