专栏首页stream process二路归并排序的java实现

二路归并排序的java实现

转载请注明出处 http://www.cnblogs.com/dongxiao-yang/p/6410775.html

参考引言:在排序算法中快速排序的效率是非常高的,但是还有种排序算法的效率可以与之媲美,那就是归并排序;归并排序和快速排序有那么点异曲同工之妙,快速排序:是先把数组粗略的排序成两个子数组,然后递归再粗略分两个子数组,直到子数组里面只有一个元素,那么就自然排好序了,可以总结为先排序再递归;归并排序:先什么都不管,把数组分为两个子数组,一直递归把数组划分为两个子数组,直到数组里只有一个元素,这时候才开始排序,让两个数组间排好序,依次按照递归的返回来把两个数组进行排好序,到最后就可以把整个数组排好序;

public class mergesortutil {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int[] a = new int[] { 11,9,7,5,3,1,12,10,8,6,4,2 };
        

        int[] tmp = new int[a.length];
        mergesort(a,0,a.length-1,tmp);
    }

    private static void mergearray(int[] array, int start, int middle, int end,int[] tmp) {

        int first = start;
        int second = middle + 1;
        int index = start;


        while ((first <= middle) && (second <= end)) {
            if (array[first] >= array[second])
                tmp[index++] = array[second++];
            else
                tmp[index++] = array[first++];
        }
        while (first <= middle)
            tmp[index++] = array[first++];
        while (second <= end)
            tmp[index++] = array[second++];

        for (first = start; first <= end; first++)
            array[first] = tmp[first];
        
        
        System.out.println("merge is "+Arrays.toString(array));

    }

    public static void mergesort(int[] array, int start, int end,int[] tmp) {

        if (start >= end)
            return;
        int middle = ((end + start) >> 1);
        mergesort(array, start, middle,tmp);// 递归划分左边的数组
        mergesort(array, middle + 1, end,tmp);// 递归划分右边的数组
        mergearray(array, start, middle, end,tmp);// 对有序的两个数组进行合并成一个有序的数组
    }

}

程序调试输出如下

<!-- p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 11.0px Monaco} -->

merge is [9, 11, 7, 5, 3, 1, 12, 10, 8, 6, 4, 2]

merge is [7, 9, 11, 5, 3, 1, 12, 10, 8, 6, 4, 2]

merge is [7, 9, 11, 3, 5, 1, 12, 10, 8, 6, 4, 2]

merge is [7, 9, 11, 1, 3, 5, 12, 10, 8, 6, 4, 2]

merge is [1, 3, 5, 7, 9, 11, 12, 10, 8, 6, 4, 2]

merge is [1, 3, 5, 7, 9, 11, 10, 12, 8, 6, 4, 2]

merge is [1, 3, 5, 7, 9, 11, 8, 10, 12, 6, 4, 2]

merge is [1, 3, 5, 7, 9, 11, 8, 10, 12, 4, 6, 2]

merge is [1, 3, 5, 7, 9, 11, 8, 10, 12, 2, 4, 6]

merge is [1, 3, 5, 7, 9, 11, 2, 4, 6, 8, 10, 12]

merge is [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

调试过程输出结果有助于更好的理解排序过程,整个排序在数组划分到最小长度后不断进行局部排序和局部合并排序,最终合并为全数组。

参考资料

1 归并排序的原理及时间复杂度

2 白话经典算法系列之五 归并排序的实现

3 排序算法之 归并排序 及其时间复杂度和空间复杂度

<!-- p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 11.0px Monaco} -->

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PriorityBlockingQueue优先队列的二叉堆实现

    转载请注明原创地址http://www.cnblogs.com/dongxiao-yang/p/6293807.html

    sanmutongzi
  • 堆排序算法的java实现

    堆积排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素。堆排序是不稳定的排序方法,...

    sanmutongzi
  • ganglia Web前端清除当机节点

    ganglia默认如果服务器down机也不会在web前段清除该设备,官方文档介绍的办法如下:

    sanmutongzi
  • 逆序对-----归并排序

    本周遇到了一道蛮有意思的题目,分享给大家欣赏一下!这道题使用归并排序。原来在力扣上刷题时,也遇到过一次归并的思路,不过当时一知半解,就跳过去了,心想着以后遇到了...

    鹏-程-万-里
  • 归并排序

    归并排序的一切都是基于归并这一操作,具体来说就是把两个有序的小数组归并成一个有序的大数组。首先从这两个数组中各按顺序取出一个元素,将小的元素先放入大数组,大的后...

    naget
  • 数据结构|数组,栈和队列[1]

    数组的大小固定,如果存储数量过多,需要重建新数组;同时存储的数据类型单一,每个元素占用内存大小相同;添加,删除,移动操作比较慢,因为需要改变受影响的元素

    Rare0716
  • Python3之数组(array)

    当我们需要1000万个浮点数的时候,数组(array)的效率要比列表(list)要高得多,因为数组在背后存的并不是float对象,而是数字的机器翻译,也就是字节...

    周小董
  • 把stdclass object 转化成数组

    今天从接口上获取数据,用json_decode转化成发现是一个stdClass Object 。例子:

    Inkedus
  • 【numpy】新版本中numpy(numpy>1.17.0)中的random模块

    numpy是Python中经常要使用的一个库,而其中的random模块经常用来生成一些数组,本文接下来将介绍numpy中random模块的一些使用方法。

    绝命生
  • 给 iOS 开发者的 python 学习日记十二

    写在前面 我们在昨天的学习笔记讨论了 Python 基本变数类型与资料结构可以应用的属性或方法,除了基本的资料结构以外,你是否还记得 Python 可以透过引入...

    企鹅号小编

扫码关注云+社区

领取腾讯云代金券