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

释放双眼,带上耳机,听听看~!

一、动图演示

 

 

二、思路分析

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

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]; } } }

 

人已赞赏
随笔日记

hostkvm:香港VPS一律8折,CMI机房,三网直连,80Mbps带宽,带Windows

2020-11-9 4:01:41

随笔日记

代码精进之路读后感(三)

2020-11-9 4:01:43

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索