归并排序

归并排序

前言

本篇文章是排序算法系列的第四篇,学习归并排序

后面这段话将作为排序算法系列博客每一篇的开头:

为避免文中过多赘述,写在最前面:

  1. 接下来所有的排序算法讲解中,无论是思路梳理,还是代码实现,都是最终实现从小到大排序,从大到小可以学会后自行类推。
  2. 都是使用int数组进行排序,数据总量为n

归并排序

核心理念

归并排序核心思想是分治,分治法顾名思义,分开来治理,首先将一个大问题拆分成小问题,小问题逐个治理解决,最终再合起来完整的解决大问题

这里就直接说了,将一整个数组排序的问题,归并排序的思想是拆分成两个有序数组的合并问题。

我当初看到这里就马上暂停了一下,自己去想,怎么才能把一个数组排序问题,拆分成两个有序数组的合并,想了很久也没想到,感觉怎么拆也不能保证都是有序的,接着往下看了,然后晕倒!当持续的拆下去,拆成左右两个数组都只剩一个数据,一个数据当然是有序的,它们就全是有序的了......

到这里一下就豁然开朗了,先一步步拆到最底层再退回来合成到最顶层,思路就来了,首先将数组一分为二,此时的左右两边数组还不是有序的,我们要把他们都变成有序的,再重新将两个数组当做新数组继续一分为二,直到数组中只有一个数字为止,再分别将两个一个数据的数组合成一个两个数据的有序数组,再将两个两个数据的有序数组合成一个四个数据的有序数组,一直到合成回顶层。

实现思路

每一次拆分其实都是四个步骤:

  1. 判断当前数组长度是否大于1,不大于1就结束
  2. 大于1就将数组对半拆成左右两个数组
  3. 左右数组也从第一步开始执行这四个步骤
  4. 将左右数组执行有序数组合并(此时的左右数组,因为第三步的存在,一层一层进去又出来,已经是有序的了)

到这里,分治中,分的过程就通过递归达成了目的,但这个第四步还需要进一步去深入一下,将有两个序数组合并成一个有序数组,步骤如下:

  1. 准备一个长度是两数组长度和的数组,临时存放合并后的结果,用一个指针执行数组第一个位置;
  2. 用两个指针分别指向两个数组的第一个元素;
  3. 如果两个指针都没有越界就进入循环,比较两个指针处数据的大小,将小的一个放入临时数组的指针位置,临时数组指针后移,小的一个指针后移,然后再次判断是否两个指针都没有越界,进入下一次循环
  4. 直到其中一个指针越界了,说明其中一个有序数组全部放到临时数组中了,因为两个数组都是从小到大排列的有序数组,此时只需要将另一个数组中所有剩余的元素依次添加到临时数组中即可
  5. 完成上述四步,临时数组中就是合并后的结果,将它存回原来拆开的两个数组中就完成了一次合并

思路有了,大家可以试着自己写完再来看代码:

package com.zwx.sort;

/**
 * 归并排序
 *
 * @author coderZWX
 * @date 2022-06-13 16:37
 */
public class MergeSort {

    public static void mergeSort(int[] arr){
        //由于最后一次合并,需要的临时数组长度就是原数组的总长度,所以直接只创建一个最大的数组作为临时数组全程使用
        MergeSort.mergeSort(arr,0,arr.length-1,new int[arr.length]);
    }

    private static void mergeSort(int[] arr, int start, int end, int[] temp){
        //如果数组段中的数据大于等于2个,就分割成左右两边
        if (start < end){
            //中间数索引(左边的终点)
            int mid = (start + end) / 2;
            mergeSort(arr, start, mid, temp);
            mergeSort(arr, mid + 1, end, temp);
            //无论是否需要再次分割,分割完毕或不分割,都执行一次合并操作
            merge(arr,start,mid,end,temp);
        }
    }

    /**
     * 将一个数组段,按(start+end)/2为左边终点索引,分开为左右两个数组,已知左右两边分别有序(从小到大),合并为全部有序(从小到大)
     * @param arr 大数组
     * @param start 起点索引
     * @param end 终点索引
     * @param temp 临时数组
     */
    private static void merge(int[] arr, int start, int mid, int end, int[] temp) {
        //左起点为start,左终点为mid,右起点为mid+1,右终点为end
        //左指针
        int lPointer = start;
        //右指针
        int rPointer = mid + 1;
        //临时数组指针
        int t = 0;
        //当左右指针都没越界比较左右两个指针指向数据的大小,谁小就把谁放在临时数组指针位置,并将指针后移一个
        while (lPointer<= mid && rPointer<= end){
            if (arr[lPointer]<arr[rPointer]) {
                temp[t++] = arr[lPointer++];
            }else {
                temp[t++] = arr[rPointer++];
            }
        }
        //当某个指针没越界,剩余的都放入临时数组
        while (lPointer<= mid){
            temp[t++] = arr[lPointer++];
        }
        while (rPointer<= end){
            temp[t++] = arr[rPointer++];
        }
        //将排好序的temp放回arr的start到end
        int index = start;
        t = 0;
        while (index<=end){
            arr[index++] = temp[t++];
        }
    }
}

测试对比

写这篇文章的时候,和之前三篇不在同一个电脑环境测试,但我们知道之前篇章中,最快的是快速排序,这里先运行了最快的交换法快速排序,随机散列的800w数据排序,大约1100ms左右,这里的归并排序在1300ms左右,还是路逊与快速排序

但是在选择排序算法的时候,并不能无脑快速排序,各个排序都有优缺点,日常中有排序需求的时候,800w随机分散在0-8000w整数的非常散列的数据排序是很少见的,重点是理解这些排序的思想,扩宽思路,真正排序还需要具体情况具体分析。

jdk源码中,Arrays.sort()方法,也使用到了归并排序,但暂时不去看,后续介绍完其他排序算法,再来开章节阅读jdk源码中的排序

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,539评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,911评论 3 391
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 161,337评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,723评论 1 290
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,795评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,762评论 1 294
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,742评论 3 416
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,508评论 0 271
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,954评论 1 308
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,247评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,404评论 1 345
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,104评论 5 340
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,736评论 3 324
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,352评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,557评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,371评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,292评论 2 352

推荐阅读更多精彩内容