专栏首页后端Coder第五篇排序算法|归并排序

第五篇排序算法|归并排序

0x01,前言闲叙

最近几年很少看电视了,因为没时间看了,除了偶尔刷刷头条,基本上不会花大块的时间沉迷于电视剧,综艺,这或许就是短视频时代所带来的一些改变吧,我们都会深受其中。

0x02,先看下这篇文章要讲述的内容大概吧

0x03,什么是归并排序?

【百度百科介绍】归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

0x04,归并排序程序实现

public class MergeSortTest {
    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 4, 9, 8, 10, 7, 6, 5, 10, 12, 13, 15, 14};
        int left = 0;
        int right = arr.length - 1;
        mergeSort(arr, left, right);
        for (int num : arr
        ) {
            System.out.print(num + "\t");
        }
    }

    private static int[] mergeSort(int[] arr, int left, int right) {
        if (left == right) {
            return new int[]{arr[left]};
        }
        int mid = left + (right - left) / 2;
        int[] leftArr = mergeSort(arr, left, mid);
        int[] rightArr = mergeSort(arr, mid + 1, right);
        int[] newArray = new int[leftArr.length + rightArr.length];
        int m = 0;
        int i = 0;
        int j = 0;
        while (i < leftArr.length && j < rightArr.length) {
            newArray[m] = leftArr[i] < rightArr[j] ? leftArr[i] : rightArr[j];
            i++;
            j++;
            m++;
        }
        while (i < leftArr.length) {
            newArray[m++] = leftArr[i++];
        }
        while (j < rightArr.length) {
            newArray[m++] = rightArr[j++];
        }
        return newArray;
    }


}

0x05,归并排序的程序图片版

0x06,总结一下

看这道题的时候先把上面的二分查找理解一下,这样就基本上理解了如何进行划分数组的操作,数据有序合并就是正常逻辑的实现了

本文分享自微信公众号 - WwpwW(gh_245290c1861a),作者:后端Coder

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-19

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode70|最小K个数

    排序在整个工作中还是比较的常用的一种场景,排序的目的是为了更加高效的检索自己需要的数据,对于数据库优化,为什么要加索引,难道不是为了更加高效的检索自己需要的数据...

    码农王同学
  • LeetCode14|合并排序的数组

    给定两个排序后的数组 A 和 B,其中 A 的末端有足够的缓冲空间容纳 B。编写一个方法,将 B 合并入 A 并排序。

    码农王同学
  • LeetCode13|最小k个数

    有两种解法,第一种是数据装入集合,对集合进行升序排序,查找前k个元素;第二种是对数组进行排序,将k的元素装入新数组中。

    码农王同学
  • PAT (Basic Level) Practice (中文)1061 判断题

    判断题的评判很简单,本题就要求你写个简单的程序帮助老师判题并统计学生们判断题的得分。

    C you again 的博客
  • C语言 | C++动态分配与静态分配的区别

    所谓动态内存分配就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。动态内存分配不象数组等静态内存分配方法那样需要预先分配存储空间,而是由系统根...

    C语言入门到精通
  • 动态分配与静态分配的区别

    所谓动态内存分配就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。动态内存分配不象数组等静态内存分配方法那样需要预先分配存储空间,而是由系统根...

    公众号C语言与CPP编程
  • 00后小哥告诉你,何谓桶排序?

    我们经常在学校学习阶段听到木桶原理这个词,意思就是说这个木桶所能装载的水的量是由最短的那个木板决定的

    机智的程序员小熊
  • java学习之路:10.数组的基本操作(遍历,替换,排序,复制,查询)

    不知道大家有没有注意到print和println的区别,看第一块代码,会发现它会换行,而第二块代码不会,通过查找得知print+换行=println。

    花狗Fdog
  • LeetCode 215. Kth Largest Element in an Array分析

    显然最简单的思想就是排序,然后取出倒数第k个元素就可以了,我们可以直接调用内部的排序函数。

    desperate633
  • HDUOJ -----Color the ball

    Color the ball Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/327...

    Gxjun

扫码关注云+社区

领取腾讯云代金券