文档章节

Java算法之 归并排序算法

郑加威
 郑加威
发布于 2017/04/18 15:12
字数 676
阅读 8
收藏 0

基本思想:

  归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序示例:

合并方法:

设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成,两个子表长度分别为n-i +1、n-m。

  1. j=m+1;k=i;i=i; //置两个子表的起始下标及辅助数组的起始下标
  2. 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束
  3. //选取r[i]和r[j]较小的存入辅助数组rf
    如果r[i]<r[j],rf[k]=r[i]; i++; k++; 转⑵
    否则,rf[k]=r[j]; j++; k++; 转⑵
  4. //将尚未处理完的子表中元素存入rf
    如果i<=m,将r[i…m]存入rf[k…n] //前一子表非空
    如果j<=n , 将r[j…n] 存入rf[k…n] //后一子表非空
  5. 合并结束。

算法实现:

  /**
     * 归并排序
     * 简介:将两个(或两个以上)有序表合并成一个新的有序表 即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列
     * 时间复杂度为O(nlogn)
     * 稳定排序方式
     * @param nums 待排序数组
     * @return 输出有序数组
     */
    public static int[] sort(int[] nums, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            // 左边
            sort(nums, low, mid);
            // 右边
            sort(nums, mid + 1, high);
            // 左右归并
            merge(nums, low, mid, high);
        }
        return nums;
    }

    /**
     * 将数组中low到high位置的数进行排序
     * @param nums 待排序数组
     * @param low 待排的开始位置
     * @param mid 待排中间位置
     * @param high 待排结束位置
     */
    public static void merge(int[] nums, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;// 左指针
        int j = mid + 1;// 右指针
        int k = 0;

        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (nums[i] < nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }

        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = nums[i++];
        }

        // 把右边边剩余的数移入数组
        while (j <= high) {
            temp[k++] = nums[j++];
        }

        // 把新数组中的数覆盖nums数组
        for (int k2 = 0; k2 < temp.length; k2++) {
            nums[k2 + low] = temp[k2];
        }
    }

效率:

© 著作权归作者所有

共有 人打赏支持
郑加威
粉丝 145
博文 194
码字总数 402030
作品 0
杭州
架构师
私信 提问

暂无文章

腾讯面试:一条SQL语句执行得很慢的原因有哪些?

说实话,这个问题可以涉及到 MySQL 的很多核心知识,可以扯出一大堆,就像要考你计算机网络的知识时,问你“输入URL回车之后,究竟发生了什么”一样,看看你能说出多少了。 之前腾讯面试的实...

java菜分享
35分钟前
9
0
Java 基本功 之 CAS

本文首发于个人公众号《andyqian》, 期待你的关注! 前言 在Java并发编程中,我们经常使用锁对竞争资源予以并发控制,以解决资源竞争的问题。但无论是使用 Lock 还是 Synchronized,随着锁机...

andyqian
39分钟前
4
0
信号量与条件变量的区别

注意信号量与条件变量的区别 信号量内容可见:http://www.cnblogs.com/charlesblc/p/6142868.html 信号量、共享内存,以及消息队列等System V IPC三剑客主要关注进程间通信; 而条件变量、互...

shzwork
50分钟前
1
0
在VirtualBox 6.0中安装fedora 30

操作系统安装完毕后首先进行更新。 sudo dnf update 重启虚拟机后,安装VirtualBox依赖的软件包。 sudo dnf install kernel-headers kernel-devel dkms gcc 最后,安装“增强功能”。...

gugudu
58分钟前
1
0
861. Score After Flipping Matrix

为了获得最大值,我们必须保证每一行列下标小的1尽可能的多(最高位的1尽可能多)。 首先,考虑我们可以进行的操作有 翻转列,进行列操作 翻转行,进行行操作 通过行操作 我们总是可以使得第...

reter
59分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部