原创

归并排序

归并过程merge

复制一个同样的数组aux,3个索引,蓝色剪头为最终的数组中需要跟踪的索引位置,两个红色剪头是已经分别排序好的两个数组当前要考虑的元素

k为蓝色的索引,i、j分别为红色索引,第一个位置1<2(aux[j] < aux[i])所以arr[k] = aux[j]

边界条件是[l, r],起始位置是数组的左索引,终止位置是数组的右索引


代码

import java.util.*;

public class MergeSort{

    // 我们的算法类不允许产生任何实例
    private MergeSort(){}

    // 将arr[l...mid]和arr[mid+1...r]两部分进行归并
    private static void merge(Comparable[] arr, int l, int mid, int r) {

        Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);

        // 初始化,i指向左半部分的起始索引位置l;j指向右半部分起始索引位置mid+1
        int i = l, j = mid+1;
        for( int k = l ; k <= r; k ++ ){

            if( i > mid ){  // 如果左半部分元素已经全部处理完毕
                arr[k] = aux[j-l]; j ++;
            }
            else if( j > r ){   // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i-l]; i ++;
            }
            else if( aux[i-l].compareTo(aux[j-l]) < 0 ){  // 左半部分所指元素 < 右半部分所指元素
                arr[k] = aux[i-l]; i ++;
            }
            else{  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j-l]; j ++;
            }
        }
    }

    // 递归使用归并排序,对arr[l...r]的范围进行排序
    private static void sort(Comparable[] arr, int l, int r) {

        if (l >= r)
            return;

        int mid = (l+r)/2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    public static void sort(Comparable[] arr){

        int n = arr.length;
        sort(arr, 0, n-1);
    }
}

自底向上的归并排序

import java.util.*;

public class MergeSortBU{

    // 我们的算法类不允许产生任何实例
    private MergeSortBU(){}

    // 将arr[l...mid]和arr[mid+1...r]两部分进行归并
    private static void merge(Comparable[] arr, int l, int mid, int r) {

        Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);

        // 初始化,i指向左半部分的起始索引位置l;j指向右半部分起始索引位置mid+1
        int i = l, j = mid+1;
        for( int k = l ; k <= r; k ++ ){

            if( i > mid ){  // 如果左半部分元素已经全部处理完毕
                arr[k] = aux[j-l]; j ++;
            }
            else if( j > r ){   // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i-l]; i ++;
            }
            else if( aux[i-l].compareTo(aux[j-l]) < 0 ){  // 左半部分所指元素 < 右半部分所指元素
                arr[k] = aux[i-l]; i ++;
            }
            else{  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j-l]; j ++;
            }
        }
    }

    public static void sort(Comparable[] arr){

        int n = arr.length;

        // Merge Sort Bottom Up 无优化版本
        for (int sz = 1; sz < n; sz *= 2)
            for (int i = 0; i < n - sz; i += sz+sz)
                // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并
                merge(arr, i, i+sz-1, Math.min(i+sz+sz-1,n-1));
    }
}

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 快速排序

    用户6404053
  • 冒泡排序

    用户6404053
  • Java8中的接口和抽象类的区别

    今天跑了好远去面试,面试官问了上面这个问题,我是一脸懵比,抽象类我自己没写过,JAVA8对接口有什么修改完全没印象,现在来总结一下,至少下次再遇到这个问题要答上...

    用户6404053
  • 2个线性表查找的优化

    实际上,如果待查的数据比较均匀,那么1/2是一个很好的选择,一旦待查数据中的数据是极度不均匀的,那么就需要考虑插值查找法。

    大学里的混子
  • 快排

    思路:快速排序每次都是定位一个元素在数组中的绝对位置,简单说就是一个元素,在排好序后他的位置是一定的(当然快排是不稳定的),你每次选定一个元素,然后定位其排好序...

    用户6055494
  • 经典排序算法总结--冒泡、快排、插入、希尔、归并、选择

    对纵向排列的关键字序列,按照自下而上的扫描方向对两两相邻的关键字进行比较, 若为逆序(k_j < k_j-1 ),则将两个记录交换位置; 重复上述扫描排序过...

    Java团长
  • 排序算法之归并排序

    归并排序是一种非常优秀的排序算法,时间复杂度仅为O(nlogn),与选择排序和冒泡排序的O(n2)相比较,只是将n这个因子替换成了logn,但这是非常划算的一个...

    dejavu1zz
  • 排序算法之快速排序

    快速排序是一种非常优秀的排序算法,应用的也非常广泛,面试时面试官也经常让你手写一个快排,所以说学习快速排序是非常有必要的。

    dejavu1zz
  • 团体程序设计天梯赛-练习集 L1-047 装睡

    你永远叫不醒一个装睡的人 —— 但是通过分析一个人的呼吸频率和脉搏,你可以发现谁在装睡!医生告诉我们,正常人睡眠时的呼吸频率是每分钟15-20次,脉搏是每分钟5...

    C you again 的博客
  • 基本排序算法(冒泡排序 选择排序 插入排序 快速排序 归并排序 基数排序 希尔排序)

    项目地址:https://github.com/windwant/windwant-service/tree/master/algorithm

    WindWant

扫码关注云+社区

领取腾讯云代金券