`
hongjn
  • 浏览: 56613 次
  • 性别: Icon_minigender_1
  • 来自: 火星
社区版块
存档分类
最新评论

归并排序(MergeSort) Java实现

阅读更多
归并排序的Java实现:

import java.util.Arrays;

public class MergeSort {

    public static void sort(Comparable[] data, int p, int r) {

        /*
         * p = 0; r = 3; total 4;
         * q = (0 + 3) / 2; q = 1;
         * sort(0, 1); sort(2,3);
         * sort(p, q); sort(q + 1, r);
         */
        if (p < r) {
            int q = (p + r) / 2;
            sort(data, p, q);
            sort(data, q + 1, r);
            merge(data, p, q, r);
        }

    }

    private static void merge(Comparable[] data, int p, int q, int r) {
        Comparable[] left = Arrays.copyOfRange(data, p, q + 1);

        Comparable[] right = Arrays.copyOfRange(data, q + 1, r + 1);

        int i = 0;
        int j = 0;
        int k = 0;
        while (k < r - p + 1) {
            if (i == left.length) {
                data[p + k] = right[j++];
            }
            else if (j == right.length) {
                data[p + k] = left[i++];
            }
            else if (left[i].compareTo(right[j]) < 0) {
                data[p + k] = left[i++];
            }
            else {
                data[p + k] = right[j++];
            }
            k++;
        }

    }

}

2
2
分享到:
评论

相关推荐

    java实现归并排序

    Java实现归并排序 Java 实现归并排序是一种常用的排序算法,通过分治策略将原始数组分成小组,然后对每个小组进行排序,最后将排序好的小组合并成一个有序数组。下面是 Java 实现归并排序的知识点总结: 基本思想 ...

    归并排序的java实现.docx

    归并排序是一种高效的排序算法,基于分治策略。...通过上述分析,我们可以看到,归并排序的Java实现利用了分治策略,将数组拆分成更小的部分,然后合并这些部分以达到排序的目的。这种方法确保了排序的效率和稳定性。

    Java实现归并排序

    在Java中实现归并排序,主要涉及到以下几个关键步骤: 1. **分割(Divide)**:将原始数组分为两个相等(或接近相等)的子数组。这通常通过取数组中间索引来完成。例如,如果数组长度为`n`,则可以将前`n/2`个元素...

    归并排序Java_归并排序_

    以上就是归并排序的基本原理和Java实现,通过`MergeSort`类,你可以方便地对任何整数数组进行排序。归并排序在许多实际场景中都发挥着重要作用,例如大数据处理、文件排序等。了解并掌握这种排序算法对于提升编程...

    归并排序(JAVA)

    归并排序是一种经典的排序算法,基于分治策略。在Java中实现归并排序,我们可以将一个大数组分成两个...通过深入理解和实践`MergeSort.java`文件,你可以掌握归并排序的基本原理和实现技巧,进一步提升自己的编程能力。

    Java实现归并排序.rar

    归并排序是一种经典的排序算法,基于分治策略。...总的来说,Java实现归并排序涉及的主要知识点包括分治策略、递归、数组操作以及合并算法的设计。通过熟练掌握这些概念,可以有效地在实际编程中实现高效的排序功能。

    归并排序介绍和java代码实现

    归并排序是一种高效的排序算法,基于分治策略。它的核心思想是将大问题分解为小问题,然后逐一解决,最后将结果合并。...通过理解其工作原理和Java实现,开发者可以在实际项目中灵活运用归并排序来优化算法性能。

    算法-归并排序(java)(csdn)————程序.pdf

    下面将详细介绍归并排序算法的java实现。 什么是归并排序? 归并排序是一种基于分治策略的排序算法。其基本思想是将一个大的无序数组分成两个或多个小数组,递归地将每个小数组排序,然后将排好序的子数组合并成一...

    java实现的shell排序快速排序归并排序堆排序

    `mergesort.java`文件应该包含了归并排序的分治过程。 4. **堆排序**: 堆排序是由Napier和Rabin在1962年提出,它利用了堆这种数据结构。堆是一个近似完全二叉树的结构,并同时满足堆的性质:即子节点的键值或索引...

    java归并排序

    在Java中实现归并排序,我们可以分别实现递归版和非递归版,这两种方法各有其特点和适用场景。 ### 1. 分治策略 归并排序的核心是分治法,它将一个大数组分为两个相等或接近相等的子数组,分别对这两个子数组进行...

    java实现归并排序算法

    在Java中,我们可以看到一个典型的归并排序实现。`mergeSort()`方法是归并排序的主函数,它接受一个整数数组`a`,一个临时数组`tmp`以及两个表示子序列范围的索引`left`和`right`。`mergeSort()`首先检查左边界是否...

    Java实现归并排序算法(源代码)

    ### Java实现归并排序算法(源代码)知识点详解 #### 一、归并排序概述 归并排序是一种经典的排序算法,其核心思想是分而治之。它将一个大问题分解为若干个相同的小问题来解决,最终通过合并这些小问题的解来得到...

    归并排序及的java实现.pdf

    在Java中实现归并排序,我们可以创建一个名为`MergeSort1`的类,并定义一个主函数`main`来接收用户输入的待排序数组。首先,通过`Scanner`类获取用户输入的数字个数和具体数字,将这些数字存储到一个整型数组`a`中。...

    java编程实现分治法归并排序

    ### Java编程实现分治法归并排序 #### 分治法基本思想 分治法是一种将大问题分解成小问题,并通过解决这些小问题来解决原始问题的方法。这种方法的基本步骤包括: 1. **分解**:将一个问题分解为若干个规模较小的...

    可视化归并排序

    在Java中实现归并排序,你需要定义一个方法来进行这些操作。`mergeSort()`方法会递归地分割数组,而`merge()`方法则负责合并已排序的子数组。`merge()`通常使用两个指针,分别从两个子数组的开头开始,每次选择较小...

    归并排序算法(Merge Sort)的Java实现

    归并算法的简单举例

    详解Java常用排序算法-归并排序

    在Java中,归并排序可以通过递归和迭代两种方式实现。递归实现的优点是代码简洁易懂,但缺点是递归调用会占用系统资源,可能引发StackOverflowError异常。迭代实现的优点是可以避免递归调用,但缺点是代码较为复杂。...

    给定一个数列,用归并排序算法把它排成升序。

    #### 二、归并排序实现步骤 1. **递归分割**:不断将序列分割成更小的子序列,直到每个子序列只有一个元素。 2. **合并操作**:将相邻的两个子序列合并为一个新的有序序列。 3. **递归返回**:当所有子序列都排序...

    八种排序算法原理及Java实现( 冒泡排序+快速排序直接插入排序+希尔排序+选择排序+归并排序+基数排序)

    八种排序算法原理及Java实现是排序算法中的一种,包括冒泡排序、快速排序、直接插入排序、希尔排序、选择排序、归并排序和基数排序等。 冒泡排序是八种排序算法中的一种,属于交换排序。冒泡排序的基本思想是重复...

Global site tag (gtag.js) - Google Analytics