java归并排序

作者: 夜亦明 | 来源:发表于2018-12-14 15:04 被阅读6次

概述

归并排序与快速排序相同,同样是借鉴二叉树的思想,时间复杂度O(n),与快速排序一样是大量数据排序的最优方式之一。

思路分析

归并排序是将目标数组分成左右两个数组,左右两个数组必须是有序的,然后对这两个数组合并从而实现排序。对于任意的数组都可以将所有的数据分成若干个数组,每个数组中都只有一个元素,然后两两合并。(因此,归并排序的内存开销会比快速排序多)

代码实现

  private void mergeSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) >> 1;
        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);
        merge(array, left, mid + 1, right);
    }

    private void merge(int[] array, int left, int mid, int right) {
        int leftSize = mid - left;
        int rightSize = right - mid + 1;
        int[] leftArray = new int[leftSize];
        int[] rightArray = new int[rightSize];
        System.arraycopy(array, left, leftArray, 0, leftSize);
        System.arraycopy(array, mid, rightArray, 0, rightSize);
        int index=left;
        int leftIndex = 0;
        int rightIndex = 0;
        while (leftIndex<leftSize&&rightIndex<rightSize){
            if(leftArray[leftIndex]<rightArray[rightIndex]){
                array[index++] = leftArray[leftIndex++];
            }else {
                array[index++] = rightArray[rightIndex++];
            }
        }
        while (leftIndex<leftSize){
            array[index++] = leftArray[leftIndex++];
        }
        while (rightIndex<rightSize){
            array[index++] = rightArray[rightIndex++];
        }
    }

测试代码

 @Test
    public void testMergeSort() {
        int[] array = new int[]{1, 3, 4, 10, 2, 5, 6, 9, 7, 8};
        mergeSort(array, 0, array.length - 1);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }

结果打印

1
2
3
4
5
6
7
8
9
10

相关文章

  • 归并排序

    归并排序Java实现

  • 归并排序

    归并排序 代码实现(java):

  • 常用排序算法的Java实现

    冒泡、插入、选择、归并、快速排序的Java实现

  • 归并排序

    自顶向下的归并排序 java描述

  • 面试知识点

    排序冒泡排序快速排序选择排序插入排序二路归并 查找二分查找 排序和查找的java实现 java语言Java字符串字...

  • Java代码实现归并排序

    Java代码实现归并排序 归并排序(Merge Sort) 思路:如果要排序一个数组,我们先把数组从中间分成前后两...

  • 快排 、 归并排序----复习

    分治思想在归并排序之中可以很好地体现出来。 归并排序: 下面是程序java static public void...

  • 排序算法Java实现

    本文会通过Java语言实现:冒泡排序,插入排序,选择排序,归并排序,快速排序,桶排序,计数排序,基数排序,希尔排序...

  • 排序

    八大排序算法 一、归并排序 递归及非递归的JAVA实现 二、快速排序 快排算法JAVA实现 三、堆排序 堆排序堆排...

  • 排序算法

    约定 选择排序 冒泡排序 插入排序 希尔排序 归并排序1. 归并方法2. 自顶向下归并排序3. 自底向上归并排序 ...

网友评论

    本文标题:java归并排序

    本文链接:https://www.haomeiwen.com/subject/thdghqtx.html