归并排序--java实现

代码如下:

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] intArr = SortBase.generateIntArr(1, 100, 20);
        System.out.println(Arrays.toString(intArr));

        // 使用java自带排序算法,用于结果比对
        int[] tmp = new int[intArr.length];
        System.arraycopy(intArr, 0, tmp, 0, intArr.length);
        Arrays.sort(tmp);
        System.out.println(Arrays.toString(tmp));

        solution(intArr, tmp, 0, intArr.length - 1);
        System.out.println(Arrays.toString(intArr));
    }

    public static void solution(int[] arr, int[] tmp, int start, int end) {
        if (start >= end) {
            return;
        }

        int mid = start + ((end - start) >> 1);
        int start1 = start;
        int end1 = mid;
        int start2 = mid + 1;
        int end2 = end;

        // System.out.println(start1+"_"+end1+"_"+start2+"_"+end2);

        solution(arr, tmp, start1, end1);
        solution(arr, tmp, start2, end2);
        int k = start;
        while (start1 <= end1 && start2 <= end2) {
            tmp[k++] = arr[start1] <= arr[start2] ? arr[start1++] : arr[start2++];
        }

        while (start1 <= end1) {
            tmp[k++] = arr[start1++];
        }

        while (start2 <= end2) {
            tmp[k++] = arr[start2++];
        }

        for (k = start; k <= end; k++) {
            arr[k] = tmp[k];
        }
    }
}

个人资料
时海
等级:8
文章:272篇
访问:16.0w
排名: 2
上一篇: JVM常见面试题
下一篇:图的深度遍历+广度遍历--java
标签: 算法、面试题
隐藏