当前位置:首页 > 开发 > 编程语言 > Java > 正文

归并排序(MergeSort) Java实现

发表于: 2011-09-17   作者:hongjn   来源:转载   浏览次数:
摘要: 归并排序的Java实现: import java.util.Arrays; public class MergeSort { public static void sort(Comparable[] data, int p, int r) { /* * p = 0; r = 3; total 4; *
归并排序的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++;
        }

    }

}

归并排序(MergeSort) Java实现

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个
前面一篇博文写了归并排序的算法实现,虽然做了些注释,但没有写归并排序的原理,这篇就补上,同时
前面一篇博文写了归并排序的算法实现,虽然做了些注释,但没有写归并排序的原理,这篇就补上,同时
前面一篇博文写了归并排序的算法实现,虽然做了些注释,但没有写归并排序的原理,这篇就补上,同时
1 归并排序(MergeSort) 归并排序最差运行时间是O(nlogn),它是利用递归设计程序的典型例子。 归并
并归排序: 将两个或两个以上的有序数组组合成一个新的有序数组,叫并归排序 排序过程 1、 设初始数
起源:冯·诺依曼最早在EDVAC上实现 基本思想: 将数组一分为(Divide array into two halves) 对每
归并排序的算法实现 归并排序的基本思想是: 将待排序元素分成大小大致相同的两个子集合,分别对两
近最研究元素排序,稍微总结一下,以后继承补充: 近最决议天每学点数据结构与算法,写客博来促督自
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号