文档章节

排序算法之归并排序

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

一、分治法的思想

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

通常分治法是递归的。

二、归并排序

归并排序就是利用分治法,把无序的数列拆分成多个子数列,子数列再拆分成多个子数列,直至只子数列只有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较小的时候是不如插入排序的。所以我们可以使用归并排序划分,到一定数的时候使用插入排序进行底层的排序,这样优化起来就非常合理了。

© 著作权归作者所有

共有 人打赏支持
Lubby
粉丝 54
博文 92
码字总数 49445
作品 0
杭州
程序员
线程基础:多任务处理(16)——Fork/Join框架(排序算法性能补充)

1、概述 在之前的一篇文章《线程基础:多任务处理(13)——Fork/Join框架(解决排序问题)》中,我们使用了fork/join框架提高归并排序的性 能。那篇文章发布后,有的读者联系我,觉得单就归...

yinwenjie
2017/06/06
0
0
排序算法总结(一)---- 直接插入排序,希尔排序(java实现)

一、概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 二、稳定性,时间复杂度...

ljheee
2017/04/08
0
0
Leetcode:148_Sort List | O(nlogn)链表排序 | Medium

题目:Sort List Sort a linked list in O(n log n) time using constant space complexity 看题目有两个要求:1)时间复杂度为O(nlogn);2)空间复杂度为常数,即不能增设额外的空间。 满足...

chambai
2014/10/07
0
0
java排序之快速排序、归并排序、基数排序

前两篇说了Java排序中的冒泡、选择、插入、希尔等排序算法,今天就探讨一下剩下的三种常用排序。 快速排序: 当要求时间最快时,就可以用快速排序算法。 选择第一个数为p,小于p的数放在左边...

野小疯
06/05
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

百度贴吧发送gif图片的限制

百度贴吧中不可以发送超过500k的gif图片,同时尺寸不能超过700个像素。

gugudu
20分钟前
1
0
eclipse中查找所有汉字

今天遇到需要对中文翻译为英文的情况,需要查找一下项目中出现的所有汉字。我们可以使用快捷键Ctrl+H,在搜索一栏输入:[^\x00-\xff],记得勾选正则表达式。 备注: [\x00-\xff] 是 0 - 255的...

hengbao5
21分钟前
2
0
HBase常用操作命令

HBase – Hadoop Database,是一个高可靠性、高性能、面向列、可伸缩的分布式存储系统,利用HBase技术可在廉价PC Server上搭建起大规模结构化存储集群。 HBase是Google Bigtable的开源实现,...

飓风2000
25分钟前
1
0
天创恒达TC TC6C0更新固件包

天创恒达TC TC6C0 升级完 登录密码 admin、000000

yizhichao
27分钟前
1
0
阿里云总裁胡晓明:“这些新杭州故事,明天将会在更多城市发生”

摘要: 9月19日,2018杭州·云栖大会现场,杭州城市大脑2.0正式发布,管辖范围扩大28倍,覆盖面积增至420平方公里,相当于65个西湖大小。 ET城市大脑等数字化城市解决方案,掀开了“杭州故事...

阿里云官方博客
28分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部