归并排序算法详解,归并算法的时间复杂度

2020-04-27 19:04栏目:编程
TAG: java

归并排序,这是采用分治法的一种典型应用,也就是分治替换的原则,对一个序列进行分治,然后使其有序,使其有序的关键便是对分组后的序列再次分治,一直如此到最后进行比较替换(递归)。
然后归并成一个有序序列,将2个序列进行比较交换的原理是采用双指针方法,在开始的时候,同时指向2个序列的头节点,然后预留出一个2个序列之和的新序列用来存放新的有序数据集,一次如此,直到最后整个序列有序。
 
解答思路:
将n个元素从中间切开,分成两部分。(左边可能比右边多1个数)
将步骤1分成的两部分,再分别进行递归分解。直到所有部分的元素个数都为1。
从最底层开始逐步合并两个排好序的数列。
记住,我们规定的是比较的2个数组都是有序的,意味着当我们分治到每个数组为1个元素时,便是有序的。然后进行归并
归并的优势,时间复杂度小,为nlogn ,但是空间复杂度大,也就意味着比较占内存。

 
public class MergeSortTest {
 
    public static void main(String[] args) {
        int[] arr = new int[] {5, 4, 7, 9, 3, 8, 2, 1, 6};
        int[] sort = mergeSort(arr, 0, arr.length - 1);
        for (int num : sort) {
            System.out.println(num);
        }
    }
 
    private static int[] mergeSort(int[] arr, int l, int r) {
        // 如果索引下标相等则直接返回
        if (l == r) {
            return new int[] {arr[l]};
        }
 
        // 获取分段索引下标
        int segment = l + (r - l) / 2;
        // 左边有序的数组,这里采用递归调用就是为了分治到1个元素为止
        int[] leftArr = mergeSort(arr, l, segment);
        // 右边有序的数组
        int[] rightArr = mergeSort(arr, segment + 1, r);
 
        // 那么如何保证有序呢?,因为我们分治的元素归并后都保持有序,所以直接进行比较交换即可
        // 采用双指针来完成
        int[] newArr = new int[leftArr.length + rightArr.length];
        int k = 0;
        int i = 0;
        int j = 0;
        // 归并
        while (i < leftArr.length && j < rightArr.length) {
            newArr[k++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
        }
        // 如果leftArr未排完,则直接插入到最后
        while (i < leftArr.length) {
            newArr[k++] = leftArr[i++];
        }
 
        while (j < rightArr.length) {
            newArr[k++] = rightArr[j++];
        }
 
        return newArr;
    }
 
//    public static int[] mergeSort(int[] nums, int l, int h) {
//        if (l == h)
//            return new int[] { nums[l] };
//
//        int mid = l + (h - l) / 2;
//        int[] leftArr = mergeSort(nums, l, mid); //左有序数组
//        int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组
//        int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组
//
//        int m = 0, i = 0, j = 0;
//        while (i < leftArr.length && j < rightArr.length) {
//            newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
//        }
//        while (i < leftArr.length)
//            newNum[m++] = leftArr[i++];
//        while (j < rightArr.length)
//            newNum[m++] = rightArr[j++];
//        return newNum;
//    }
//    public static void main(String[] args) {
//        int[] nums = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };
//        int[] newNums = mergeSort(nums, 0, nums.length - 1);
//        for (int x : newNums) {
//            System.out.println(x);
//        }
//    }

本文来自网络,不代表山斋月平台立场,转载请注明出处: https://www.shanzhaiyue.top