Java实现归并排序

这篇具有很好参考价值的文章主要介绍了Java实现归并排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

归并排序是一种分治算法,其基本思想是将数组分成两部分,分别进行排序,然后将结果合并。这种算法是分治法的典型应用。下面的Java代码实现了归并排序,包括递归和非递归两种方式。

代码解读

递归方法实现

public static void mergeSort1(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    process(arr, 0, arr.length - 1);
}

递归方法 mergeSort1 首先检查输入数组 arr 是否为空或长度小于2,若是则直接返回。然后调用 process 方法对数组进行排序。

public static void process(int[] arr, int L, int R) {
    if (L == R) { // base case
        return;
    }
    int mid = L + ((R - L) >> 1);
    process(arr, L, mid);
    process(arr, mid + 1, R);
    merge(arr, L, mid, R);
}

process 方法是递归排序的核心,它将数组从中间分成两部分,然后对每一部分分别调用 process 方法进行排序,最后调用 merge 方法将两部分合并。

非递归方法实现

public static void mergeSort2(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    int N = arr.length;
    int mergeSize = 1;
    while (mergeSize < N) {
        int L = 0;
        while (L < N) {
            if (mergeSize >= N - L) {
                break;
            }
            int M = L + mergeSize - 1;
            int R = M + Math.min(mergeSize, N - M - 1);
            merge(arr, L, M, R);
            L = R + 1;
        }
        if (mergeSize > N / 2) {
            break;
        }
        mergeSize <<= 1;
    }
}

非递归方法 mergeSort2 的实现思路是通过一个外部循环控制合并的大小 mergeSize ,然后在内部循环中对数组进行分组和合并。

合并代码

private static void merge(int[] arr, int l, int m, int r) {
        //  生成一个临时数组
        int[] help = new int[r - l + 1];
        int i = 0;//记录数组元素
        int p1 = l;//左组指针
        int p2 = m + 1;//右组指针
        //while循环规定指针的界限
        while (p1 <= m && p2 <= r) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            //左组有剩余元素,不包括生成的临时组,直接将其加入
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }

    }
    

这段代码是归并排序中的合并部分,它的作用是将两个已经有序的子数组合并成一个有序的数组。其中,参数arr是待排序的数组,参数l、m、r分别是代表数组左、中、右三个位置的下标。首先,代码创建了一个临时数组help,表示辅助排序的数组,它的长度就是左右两个子数组需要合并的元素个数。然后,代码定义了一个指针i,用于记录help数组中元素的下标。接着,定义了两个指针p1、p2,分别表示左、右两个子数组的起始位置。这里使用while循环来遍历两个子数组的元素,并将其依次放入辅助数组help中。判断当前左右两个数组中哪个元素更小,就将其放入help数组中,并让相应的指针向右移动。当遍历完其中一个子数组后,如果另一个子数组还有剩余的元素,那么将这些元素直接放入help数组中即可。最后,在合并完成后,需要将help数组中排好序的元素复制回原数组arr对应的位置。

测试

public static void main(String[] args) {
    int testTime = 500000;
    int maxSize = 100;
    int maxValue = 100;
    System.out.println("测试开始");
    for (int i = 0; i < testTime; i++) {
        int[] arr1 = generateRandomArray(maxSize, maxValue);
        int[] arr2 = copyArray(arr1);
        mergeSort1(arr1);
        mergeSort2(arr2);
        if (!isEqual(arr1, arr2)) {
            System.out.println("出错了!");
            printArray(arr1);
            printArray(arr2);
            break;
        }
    }
    System.out.println("测试结束");
}

main 方法中,我们进行了大量的测试,包括生成随机数组,复制数组,然后使用两种方法进行排序,并检查排序结果是否相等。

总结

归并排序是一种非常高效的排序算法,其时间复杂度是O(nlogn),空间复杂度是O(n),它是一种稳定的排序算法。以上就是Java实现归并排序的全部内容,希望对大家有所帮助。文章来源地址https://www.toymoban.com/news/detail-565741.html

到了这里,关于Java实现归并排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java实现归并排序

    归并排序是一种分治算法,其基本思想是将数组分成两部分,分别进行排序,然后将结果合并。这种算法是分治法的典型应用。下面的Java代码实现了归并排序,包括递归和非递归两种方式。 递归方法实现 递归方法 mergeSort1 首先检查输入数组 arr 是否为空或长度小于2,若是则

    2024年02月16日
    浏览(23)
  • 插入、希尔、归并、快速排序(java实现)

    目录 插入排序 希尔排序 归并排序 快速排序 插入排序 排序原理: 1.把所有元素分为两组,第一组是有序已经排好的,第二组是乱序未排序。 2.将未排序一组的第一个元素作为插入元素,倒序与有序组比较。 3.在有序组中找到比插入元素小或者大的元素,将插入元素放入该位

    2024年02月13日
    浏览(38)
  • 【Java数据结构与算法】Day2-高级排序(希尔、归并、快速、计数)

    ✅作者简介:热爱Java后端开发的一名学习者,大家可以跟我一起讨论各种问题喔。 🍎个人主页:Hhzzy99 🍊个人信条:坚持就是胜利! 💞当前专栏:【Java数据结构与算法】 🥭本文内容:Java数据结构与算法中的比较高级的排序,希尔排序、归并排序、快速排序、计数排序

    2024年02月02日
    浏览(62)
  • 【数据结构与算法】归并排序详解:归并排序算法,归并排序非递归实现

    归并排序是一种经典的排序算法,它使用了分治法的思想。下面是归并排序的算法思想: 递归地将数组划分成较小的子数组,直到每个子数组的长度为1或者0。 将相邻的子数组合并,形成更大的已排序的数组,直到最终得到一个完全排序的数组。 归并排序的过程可以分为三

    2024年01月22日
    浏览(66)
  • 【排序算法】 归并排序详解!深入理解!思想+实现!

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 算法—排序篇 🌄 莫道桑榆晚,为霞尚满天! ​ 什么是归并?通过归并排序就能让数据有序?分治法是怎么在归并排序上应用的?本文将对归并排序进行细致入微的讲解,庖丁解牛般让你彻底明白归并排序! 归并排序(MERGE-SORT)是建

    2024年02月08日
    浏览(42)
  • 八大排序算法之归并排序(递归实现+非递归实现)

    目录 一.归并排序的基本思想 归并排序算法思想(排升序为例) 二.两个有序子序列(同一个数组中)的归并(排升序) 两个有序序列归并操作代码: 三.归并排序的递归实现 递归归并排序的实现:(后序遍历递归) 递归函数抽象分析:  四.非递归归并排序的实现 1.非递归归并排序算法思想

    2024年02月03日
    浏览(39)
  • 归并排序(Java)

            归并排序是常见的八大排序算法之一,归并排序也是一种时间复杂度比较好的一种算法,为0(n*logn)级别。         归并排序可以用递归和非递归两种方式来实现,当然,递归方法是比较简单的,而非递归则是相对而言比较难的一种思路。         归并排序的总体思

    2024年02月21日
    浏览(23)
  • 【排序算法】 归并排序详解!深入理解!思想+源码实现!

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 算法—排序篇 🌄 莫道桑榆晚,为霞尚满天! ​ 什么是归并?通过归并排序就能让数据有序?分治法是怎么在归并排序上应用的?本文将对归并排序进行细致入微的讲解,庖丁解牛般让你彻底明白归并排序! 归并排序(MERGE-SORT)是建

    2024年02月06日
    浏览(43)
  • 【数据结构与算法】:非递归实现快速排序、归并排序

    🔥 个人主页 : Quitecoder 🔥 专栏 :数据结构与算法 上篇文章我们详细讲解了递归版本的快速排序,本篇我们来探究非递归实现快速排序和归并排序 快速排序的非递归实现主要依赖于栈(stack)来模拟递归过程中的函数调用栈。递归版本的快速排序通过递归调用自身来处理子

    2024年03月24日
    浏览(52)
  • [数据结构 -- 手撕排序算法第七篇] 递归实现归并排序

    目录 1、归并的思想 2、归并排序的思想 2.1 基本思想 2.2 图解分析 3、归并排序递归版本代码实现 3.1 代码解析 3.2 注意事项 3.2.1错误划分:[begin, mid-1],[mid, end] 3.2.2 正确划分:[begin, mid], [mid+1, end] 4、归并排序的测试 5、时间复杂度、空间复杂度分析 5.1 时间复杂度 5.2 空间复杂

    2024年02月16日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包