文档章节

排序算法之归并排序

Lubby
 Lubby
发布于 2015/10/08 20:09
字数 565
阅读 115
收藏 5

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

一、分治法的思想

把复杂的问题分解,再分解,成为很小的问题,解决这些小问题之后合并,再合并。这就是分治法的思想。

通常分治法是递归的。

二、归并排序

归并排序就是利用分治法,把无序的数列拆分成多个子数列,子数列再拆分成多个子数列,直至只子数列只有2个数,然后排序,合并,再排序,在合并。。。直到只剩一个有序的数列。

归并排序算法的核心就是:两个各自有序的数列合并成一个完全有序的数列。这个过程可以说很简单,就是从两个数列开头选出最小的数,放入第三个数列中,然后较小的数的指标后移,继续重复操作。直到其中一个数列全部被放入队列中,此时另一个队列剩下的全部数放入第三个数列。

归并排序的时间复杂度是O(nlgn)

如图所示:


三、Java代码实现

public class MergeSort {
    public static void main(String[] args) {
        int a[] = {5,3,2,8,7,6,10,20,30,11,22,33,44,100,60,200};

        mergeSort(a, 0, a.length - 1);

        for (int i : a) {
            System.out.println(i);
        }
    }

    //递归拆分数列
    public static void mergeSort(int[] a, int low, int high) {
        int middle = (low + high) / 2;
        if (low < high) {
            mergeSort(a, low, middle);
            mergeSort(a, middle + 1, high);
            merge (a, low, middle, high);
        }
    }

    //合并两段有序数列
    public static void merge(int[] a, int low, int middle, int high) {
        int n1 = middle - low + 1;
        int n2 = high - middle;

        int[] l = new int[n1];
        int[] r = new int[n2];

        for (int i = low, j = 0; i <= middle; i++, j++) {
            l[j] =a[i];
        }

        for (int i = middle + 1, j= 0; i <= high; i++, j++) {
            r[j] = a[i];
        }

        int i = 0;
        int j = 0;
        int k = low;
        while(i < n1 || j < n2) {
            if (i < n1 && j < n2) {
                if (l[i] < r[j]) {
                    a[k++] = l[i];
                    i++;
                }else {
                    a[k++] = r[j];
                    j++;
                }
            } else if (i < n1) {
                a[k++] = l[i];
                i++;
            } else if (j < n2) {
                a[k++] = r[j];
                j++;
            }
        }
    }
}

四、思考归并排序的优化。

归并排序的时间复杂度是nlgn ,插入排序的时间复杂度是n^2。

归并排序在n较小的时候是不如插入排序的。所以我们可以使用归并排序划分,到一定数的时候使用插入排序进行底层的排序,这样优化起来就非常合理了。

上一篇: mysql中的锁
Lubby
粉丝 55
博文 126
码字总数 73021
作品 0
杭州
程序员
私信 提问
加载中
请先登录后再评论。
[java初探06]__排序算法的简单认识

今天,准备填完昨天没填的坑,将排序算法方面的知识系统的学习一下,但是在简单的了解了一下后,有些不知如何组织学习了,因为排序算法的种类,实在是太多了,各有优略,各有适用的场景.有些不知所措...

osc_gni094m4
2019/04/07
9
0
C++版 归并排序

在原作者基础上加入注释 原作者:https://www.cnblogs.com/agui521/p/6918229.html 归并排序:归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为...

osc_rnrep3wi
2019/08/22
0
0
排序算法(归并排序)

  关于排序算法,常见的大致有:冒泡排序、插入排序、选择排序、快速排序、归并排序、桶排序、计数排序等。每一种排序算法都有它们各自的优劣和适用场景。一般可以从这么几个角度来衡量排序...

osc_kzwkjl9k
2019/07/05
2
0
数据结构与算法(C/C++版)【排序】

第八章《排序》 一、直接插入排序 //直接插入排序//算法思想:每趟将一个待排的关键字按照其值的大小插入到已经排好的部分有序序列的适当位置上,直到所有待排关键字都被插入到有序序列中为止...

osc_z7ezpf37
2018/06/20
2
0
数据结构与算法学习笔记二: 排序算法

  最经典最常用的排序算法:冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、计数排序、桶排序、基数排序。 在这些排序算法中如果按照时间复杂度来分类大致可分为三类: O(...

osc_cgllnrkd
06/22
5
0

没有更多内容

加载失败,请刷新页面

加载更多

Free RTOS学习随笔(1),临界区代码

Free RTOS学习随笔(1),临界区代码 基本介绍 Free RTOS中临界区代码常用函数 任务级临界代码保护 调用方式 实现原理 中断级临界代码保护 调用方式 实现原理 基本介绍 临界区代码指的是那些...

osc_ho8dcqsx
10分钟前
5
0
STM32单片机驱动步进电机—简单篇

STM32单片机驱动步进电机(一) 驱动电机运动 软件:Keil5 设备:步进电机(17HS4401)、驱动器、单片机(STM32F103) 接线方式: 电机与驱动器:黑A+,绿A-,红B+,蓝B- 驱动器与单片机:M...

osc_2qah5avr
10分钟前
18
0
龙芯开源社区上线.NET主页

龙芯团队从2019年7 月份开始着手.NET Core的MIPS64支持研发,经过将近一年的研发,在2020年6月18日完成了里程碑性的工作,在github CoreCLR 仓库:https://github.com/gsvm/coreclr, 随后受...

osc_923iryp1
12分钟前
9
0
计算机组成原理笔记(二)

我的博客: https://www.luozhiyun.com/ 浮点数和定点数 我们先来看一个问题,在Chrome浏览器里面通过开发者工具,打开浏览器里的Console,在里面输入“0.3 + 0.6”: >>> 0.3 + 0.60.8999...

osc_1psr53ow
13分钟前
13
0
Vue PDF文件预览vue-pdf

最近做项目,遇到预览PDF这个功能,在网上找了找,大多推荐的是pdf.js,不过在Vue中还是想偷懒直接npm组件,最后找到了一个还不错的Vue-pdf 组件,GitHub地址:https://github.com/FranckFreiburge...

osc_1i3ltp99
14分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部