算法-归并排序-JAVA

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

下面是Java实现归并排序的示例代码:

public class MergeSort {
    public void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int[] temp = new int[arr.length];
        mergeSort(arr, temp, 0, arr.length - 1);
    }

    private void mergeSort(int[] arr, int[] temp, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSort(arr, temp, left, mid);
        mergeSort(arr, temp, mid + 1, right);
        merge(arr, temp, left, mid, right);
    }

    private void merge(int[] arr, int[] temp, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = left;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        for (int index = left; index <= right; index++) {
            arr[index] = temp[index];
        }
    }
}

在归并排序中,首先进行递归地将数组划分为更小的子数组,然后进行合并操作。在合并操作中,将两个有序的子数组合并成一个有序的数组。

上述代码实现了归并排序的主要逻辑。mergeSort方法用于调用归并排序的入口,它接受待排序的数组作为参数,并创建一个额外的临时数组。mergeSort方法会递归地将数组划分为更小的子数组,然后调用merge方法将两个子数组合并。

merge方法中,使用三个指针ijk分别指向左子数组、右子数组和临时数组的位置。通过比较左指针和右指针指向的元素大小,将较小的值复制到临时数组中,并同时移动指针。最后,将临时数组中的元素复制回原始数组中。

要使用归并排序,只需创建一个MergeSort对象,并调用mergeSort方法,示例如下:

public class Main {
    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 5, 2, 7, 1, 4};
        MergeSort mergeSort = new MergeSort();
        mergeSort.mergeSort(arr);

        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

以上代码将输出归并排序后的有序数组:

Sorted array:
1 2 3 4 5 6 7 8

归并排序的时间复杂度为O(nlogn),其中n是待排序数组的大小。该算法是一种稳定的排序算法,适用于各种数据类型和数据量的排序。文章来源地址https://www.toymoban.com/news/detail-611817.html

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

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

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

相关文章

  • 数据结构算法--5 归并排序

    我们先看一下归并排序是怎么归并的  两个有序列表,有low指针指向2,high指针指向6,mid指针指向9 再建一个新列表,12,所以1放到列表,右指针右移一位,再比较2和3,2放入列表,左指针右移一位,以此类推,肯定有一部分列表率先没有数,这时将另一列表直接append进入新

    2024年02月11日
    浏览(48)
  • 数据结构与算法:归并排序

    在讲解归并排序前,我们先看到一个问题: 对于这样两个有序的数组,如何将它们合并为一个有序的数组? 在此我们处理这个问题的思路就是:开辟一个新的数组,然后分别安置一个指针在左右数组,利用指针遍历数组,每次对比将比较小的那个元素插入到数组的尾部。 像

    2024年01月21日
    浏览(46)
  • python算法与数据结构---排序和归并排序

    掌握归并排序的基本原理 使用python语言解答归并排序题目 原理及过程 将两个有序的数组合并成一个有序数组称为 从上往下分解:把当前区间一分为二,直至分解为若干个长度为1的子数组 从上往下的合并:两个有序的子区域两两向上合并; 体现了分治思想,稳定排序 复杂

    2024年01月21日
    浏览(72)
  • 【数据结构】排序算法(二)—>冒泡排序、快速排序、归并排序、计数排序

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.冒泡排序 2.快速排序 2.1Hoare版 2.2占坑版 2.3前后指针版 2.4三数取中对快速排序的优化 2.5非递归版 3.归

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

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

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

    目录 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日
    浏览(51)
  • 【一起学数据结构与算法】几种常见的排序(插入排序、选择排序、交换排序、归并排序)

    排序是计算机内经常进行的一种操作,其目的是将一组 “无序” 的记录序列调整为 “有序” 的记录序列。分 内部排序 和 外部排序 ,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能

    2023年04月09日
    浏览(46)
  • 【数据结构】- 排序(详细介绍几种排序算法!!!*直接插入排序,*希尔排序,*选择排序,*堆排序,*冒泡排序,*快速排序,*归并排序)

    排序无处不在,所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 内部排序 :数据元素全部放在内存中的排序。 外部排序 :数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。 今天

    2024年01月20日
    浏览(62)
  • 【算法与数据结构】归并排序的代码实现(详细图解)以及master公式的讲解

    目录 1、归并排序  1.1、算法描述  1.2、图解说明 2、代码实现  3、master公式 3.1、公式以及结论 3.2、适用于某些特殊的递归 3.3、计算归并排序的时间复杂度 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用 递归 或者说是 分治法 (Divide and Conquer)的一个非

    2024年02月08日
    浏览(62)
  • 【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)

    初窥直接插入排序我们先来看一张动图: 由动图我们可以分析出直接插入排序是从 第二个数据开始遍历 ,与 前面的数据进行比较 如果小于 则让前面的数据向前移动 自己接着向前面的数据比较 直到比较到 大于等于自己的 数据或者 没有数据能进行比较 时停止 插入当前的位

    2023年04月13日
    浏览(67)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包