归并排序 递归版和非递归版的实现(java)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/51292207

归并排序的实现(java)

本文固定链接:https://www.zybuluo.com/xujun94/note/424570

关于二分查找的,可以参考我的这篇博客二分查找的相关算法题

关于归并排序的的,可以参考我的这篇博客归并排序 递归版和非递归版的实现(java)

关于快速排序的,可以参考我的这篇博客 快速排序的相关算法题(java)

转载请注明原博客地址: http://write.blog.csdn.net/postedit/51292207

什么是归并排序

  • 归并排序其实就做两件事: 
    1. “分解”——将序列每次折半划分。
    2. “合并”——将划分后的序列段两两合并后排序。

首先我们来看一下分解是怎样实现的呢?

// 递归退出条件,及left》=right的时候 if (left < right) {    // 找出中间索引    center = (left + right) / 2;    // 对左边数组进行递归     mSort(k, 0, center);    // 对右边数组进行递归    mSort(k, center + 1, right);     // 合并   merging(k, left, center, right); }

接着合并是怎样实现的呢?

  1. 初始化一个数组,将左右数组的数进行比较,将较小的数存入中间数组
  2. 再将左右数组剩下的数存到中间数组
  3. 最后,将中间数组复制回原来的数组
 private static void merging(int[] k, int left, int center, int right) {        int tempArr[] = new int[k.length];// 存放数据的数组        // third记录中间数组的索引        int mid = center + 1;        int third = left;        int temp = left;        while (left <= center && mid <= right) {            // 从左右两个数组找出最小的数存入tempArr数组            if (k[left] < k[mid]) {                tempArr[third++] = k[left++];            } else {                tempArr[third++] = k[mid++];            }        }        // 剩余部分依次放入中间数组        while (mid <= right) {            tempArr[third++] = k[mid++];        }        while (left <= center) {            tempArr[third++] = k[left++];        }        // 将中间数组中的内容复制回原数组        while (temp <= right) {            k[temp] = tempArr[temp++];        }    }}

递归版 的源码实现如下

//下面是递归版的package com.xujun.mergesort;public class MergeSort {    static int[] a = new int[] { 20, 9, 3, 5, 26, 100, 8, -1, 7, 50, -5 };    public static void main(String[] args) {        System.out.println("before sort");        ArrayUtils.printArray(a);        mergeSort(a);        System.out.println("after sort");        ArrayUtils.printArray(a);    }    private static void mergeSort(int[] k) {        mSort(k, 0, k.length - 1);    }    private static void mSort(int[] k, int left, int right) {        int center        // 递归退出条件,及left》=right的时候        if (left < right) {            // 找出中间索引            center = (left + right) / 2;            // 对左边数组进行递归            mSort(k, 0, center);            // 对右边数组进行递归            mSort(k, center + 1, right);            // 合并            merging(k, left, center, right);        }    }    private static void merging(int[] k, int left, int center, int right) {       // 存放数据的数组        int tempArr[] = new int[k.length];        // third记录中间数组的索引        int mid = center + 1;        int third = left;        int temp = left;        while (left <= center && mid <= right) {            // 从左右两个数组找出最小的数存入tempArr数组            if (k[left] < k[mid]) {                tempArr[third++] = k[left++];            } else {                tempArr[third++] = k[mid++];            }        }        // 剩余部分依次放入中间数组        while (mid <= right) {            tempArr[third++] = k[mid++];        }        while (left <= center) {            tempArr[third++] = k[left++];        }        // 将中间数组中的内容复制回原数组        while (temp <= right) {            k[temp] = tempArr[temp++];        }    }}

下面说一下分递归版的实现思路

  1. 从归并段的长度为1开始,一次使归并段的长度变为原来的2倍。
  2. 在每趟归并的过程中,要注意处理归并段的长度为奇数和 最后一个归并段的长度和前面的不等的情况,需要做一下处理
   // 程序边界的处理非常重要        while (len <= t.length) {            for (int i = 0; i + len <= t.length - 1; i += len * 2) {        //    System.out.println("len="+len);                low = i;                mid = i + len - 1;                high = i + len * 2 - 1;                if (high > t.length - 1)                    high = t.length - 1;                merge(t, i, mid, high);            }//长度加倍            len += len;        }        return true;    }

源码如下:

package com.xujun.mergesort1;public class MergeSort2 {    /**     * 二路归并排序的递归算法-入口     *      * @param <T>     * @param t     * @return     */    public static <T extends Comparable> boolean mergeSortRecursive(T[] t) {        if (t == null || t.length <= 1)            return true;        MSortRecursive(t, 0, t.length - 1);        return true;    }    /**     * 二路归并排序的递归算法-递归主体     *      * @param <T>     * @param t     * @param low     * @param high     * @return     */    private static <T extends Comparable> boolean MSortRecursive(T[] t,            int low, int high) {        if (t == null || t.length <= 1 || low == high)            return true;        int mid = (low + high) / 2;        MSortRecursive(t, low, mid);        MSortRecursive(t, mid + 1, high);        merge(t, low, mid, high);        return true;    }    public static <T extends Comparable> boolean mergeSortNonRecursive(T[] t) {        if (t == null || t.length <= 1)            return true;        int len = 1;        int low = 0;        int mid;        int high;        // 程序边界的处理非常重要        while (len <= t.length) {            for (int i = 0; i + len <= t.length - 1; i += len * 2) {        //    System.out.println("len="+len);                low = i;                mid = i + len - 1;                high = i + len * 2 - 1;                if (high > t.length - 1)                    high = t.length - 1;                merge(t, i, mid, high);            }//长度加倍            len += len;        }        return true;    }    /**     * 将两个归并段合并成一个归并段     *      * @param <T>     * @param t     * @param low     * @param mid     * @param high     * @return     */    private static <T extends Comparable> boolean merge(T[] t, int low,            int mid, int high) {        T[] s = t.clone();// 先复制一个辅助数组        int i, j, k;// 三个指示器,i指示t[low...mid],j指示t[mid+1...high],k指示s[low...high]        for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++) {            if (t[i].compareTo(t[j]) <= 0) {                s[k] = t[i++];            } else {                s[k] = t[j++];            }        }        // 将剩下的元素复制到s中        if (i <= mid) {            for (; k <= high; k++) {                s[k] = t[i++];            }        } else {            for (; k <= high; k++) {                s[k] = s[j++];            }        }        for (int m = low; m <= high; m++) {// 将辅助数组中的排序好的元素复制回原数组            t[m] = s[m];        }        return true;    }    public static void main(String[] args) {        Integer[] arr = new Integer[] { 2, 3, 6, 8, 9, 2, 0, 1 };        long startTime = System.currentTimeMillis(); // 获取开始时间        mergeSortRecursive(arr);        long endTime = System.currentTimeMillis(); // 获取开始时间        System.out.println("执行时间:" + (endTime - startTime));        for (int i : arr) {            System.out.println(i);        }        startTime = System.currentTimeMillis(); // 获取开始时间        mergeSortNonRecursive(arr);        endTime = System.currentTimeMillis(); // 获取开始时间        System.out.println("执行时间:" + (endTime - startTime));        for (int i : arr) {            System.out.println(i);        }    }}

关于二分查找的,可以参考我的这篇博客二分查找的相关算法题

关于归并排序的的,可以参考我的这篇博客归并排序 递归版和非递归版的实现(java)

转载请注明原博客地址: http://write.blog.csdn.net/postedit/51292207

源码下载地址: http://download.csdn.net/detail/gdutxiaoxu/9565965

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏北京马哥教育

Python高级编程技巧

正文: 本文展示一些高级的Python设计结构和它们的使用方法。在日常工作中,你可以根据需要选择合适的数据结构,例如对快速查找性的要求、对数据一致 性的要求或...

50350
来自专栏AILearning

一个面试题:截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串

一个面试题: 编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串。 但 是要保证汉字不被截半个,如“我ABC”4,应该截为“我AB”,...

25590
来自专栏Java 源码分析

数据结构Stack

​ 在很多应用中,我们需要维护多个对象的集合,这种操作非常简单。我们可能想要向集合中 加入某个元素,去掉某个元素,以及遍历 集合中的元素并对他们执行某种操...

34160
来自专栏趣学算法

数据结构 第7讲 循环队列

过了一段时间,小张再也受不了这种"起早贪黑"的有车生活。为了解决胡同停车问题,小张跑了无数次居委会,终于将挡在胡同口的建筑清除,这样住在胡同尽头的小张,就可以早...

16920
来自专栏xx_Cc的学习总结专栏

iOS底层原理总结 - 探寻Runtime本质(二)

28020
来自专栏小勇DW3

LinkedHashMap 源码分析

LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致...

21230
来自专栏null的专栏

设计模式——类图以及类与类之间的关系

    设计模式在程序设计上有着很重要的作用,使用设计模式可以使得代码更容易被理解,使得代码更规范,真正实现工程化。 一、用UML表示一个类 ? 类图一般是三行...

37440
来自专栏企鹅号快讯

Python之递归函数

Python之递归函数 好久没有更新内容了,也好久没有给大家打个招呼了,小白想死你们了。今天跟大家说说Python中的递归函数。 Python是支持递归函数的。...

26980
来自专栏数据小魔方

左手用R右手Python系列之——数据框与apply向量运算

R语言与Python中的apply函数都有着丰富的应用场景,恰到好处的使用apply函数,可以避免在很多场景下书写冗余的代码,这不仅能提高代码可读性,而且提高代...

810110
来自专栏待你如初见

Day01

不推荐使用强制的类型转换,它容易丢失数据,除非不得已,并且你确定不会出现数据丢失才可以使用。

16250

扫码关注云+社区

领取腾讯云代金券