文档章节

八大排序算法——归并排序(动图演示 思路分析 实例代码java 复杂度分析)

o
 osc_a22drz29
发布于 2019/03/27 08:25
字数 685
阅读 19
收藏 0

精选30+云产品,助力企业轻松上云!>>>

一、动图演示

 

 

二、思路分析

归并排序就是递归得将原始数组递归对半分隔,直到不能再分(只剩下一个元素)后,开始从最小的数组向上归并排序

1.  向上归并排序的时候,需要一个暂存数组用来排序,

2.  将待合并的两个数组,从第一位开始比较,小的放到暂存数组,指针向后移,

3.  直到一个数组空,这时,不用判断哪个数组空了,直接将两个数组剩下的元素追加到暂存数组里,

4.  再将暂存数组排序后的元素放到原数组里,两个数组合成一个,这一趟结束。

根据思路分析,每一趟的执行流程如下图所示:

 

 

三、负杂度分析

1.  时间复杂度:递归算法的时间复杂度公式:T[n] = aT[n/b] + f(n) 

无论原始数组是否是有序的,都要递归分隔并向上归并排序,所以时间复杂度始终是O(nlog2n)

2.  空间复杂度:

  每次两个数组进行归并排序的时候,都会利用一个长度为n的数组作为辅助数组用于保存合并序列,所以空间复杂度为O(n)

 

 四、Java 代码如下

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = new int[]{3,6,4,7,5,2};
        merge(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    
    //归并
    public static void merge(int[] arr,int low,int high){
        int center = (high+low)/2;
        if(low<high){
            //递归,直到low==high,也就是数组已不能再分了,
            merge(arr,low,center);
            merge(arr,center+1,high);
            
            //当数组不能再分,开始归并排序
            mergeSort(arr,low,center,high);
            System.out.println(Arrays.toString(arr));
        }
    }
    
    //排序
    public static void mergeSort(int[] arr,int low,int center,int high){
        //用于暂存排序后的数组的临时数组
        int[] tempArr = new int[arr.length];
        int i = low,j = center+1;
        
        //临时数组的下标
        int index = 0;
        
        //循环遍历两个数组的数字,将小的插入到临时数组里
        while(i<=center && j<= high){
            
            //左边数组的数小,插入到新数组
            if(arr[i]<arr[j]){
                tempArr[index] = arr[i];
                i++;
            }else{//右边数组的数小,插入到新数组
                tempArr[index] = arr[j];
                j++;
            }
            index++;
        }
        
        //处理左半边数组多余的数据,将左半边多余的数据直接追加的临时数组的后面
        while(i<=center){
            tempArr[index] = arr[i];
            i++;
            index++;
        }
        
        //处理右半边数组多余的数据,将右半边多余的数据直接追加的临时数组的后面
        while(j<= high){
            tempArr[index] = arr[j];
            j++;
            index++;
        }
        
        //将临时数组中的数据重新放进原数组
        for (int k = 0; k < index; k++) {
            arr[k+low] = tempArr[k];
        }
    }
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

【软件工具篇02】使用Anki克服遗忘曲线

使用Anki克服遗忘曲线 艾宾浩斯遗忘曲线 百度百科:遗忘曲线由德国心理学家艾宾浩斯研究发现,描述了人类大脑对新事物遗忘的规律。人体大脑对新事物遗忘的循序渐进的直观描述,人们可以从遗...

osc_wobxrheh
17分钟前
0
0
面向对象的理解

面向对象的三大特性 封装 继承 多态 面向对象的七大原则 单一职责原则:每一个类应该专注于做一件事情。即高内聚,低耦合。类的功能要单一,体积不要过于庞大。 开闭原则:一个对象对扩展开发...

osc_2wq8ft8d
18分钟前
11
0
Laravel Redis分布式锁实现源码分析

首先是锁的抽象类,定义了继承的类必须实现加锁、释放锁、返回锁拥有者的方法。 namespace Illuminate\Cache;abstract class Lock implements LockContract{ use InteractsWithTime;...

osc_2jegjdnw
20分钟前
0
0
【HDFS篇03】HDFS客户端操作 --- 开发环境准备

存储越困难,提取越容易 HDFS客户端操作---开发环境准备 步骤一:编译对应HadoopJar包,配置Hadoop变量 步骤二:创建Maven工程,导入pom依赖 <dependencies><dependency><groupId>ju...

osc_ds5ni1ur
21分钟前
7
0
老板,来瓶辣椒酱

最近网剧《隐秘的角落》非常的火爆,结局反转让人难以预料,但前两天发生了一场堪比史诗级大片的纠纷,纠纷的结局反转让人大跌眼镜,估计是神编剧都写不出来那样的剧本...而引发这场纠纷最核...

osc_1loi8uc4
23分钟前
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部