当前位置:首页 > 开发 > 编程语言 > 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

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号