文档章节

排序算法之归并排序

Lubby
 Lubby
发布于 2015/10/08 20:09
字数 565
阅读 97
收藏 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较小的时候是不如插入排序的。所以我们可以使用归并排序划分,到一定数的时候使用插入排序进行底层的排序,这样优化起来就非常合理了。

© 著作权归作者所有

共有 人打赏支持
上一篇: mysql中的锁
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
维基百科上的算法和数据结构链接很强大

突然发现维基百科上的算法和数据结构比百度百科强多啦,图文并茂。 其实这个网站不错:http://www.sorting-algorithms.com 冒泡排序: bubble冒泡的意思 http://zh.wikipedia.org/wiki/%E5%8...

晨曦之光
2012/03/09
2.3K
1
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

没有更多内容

加载失败,请刷新页面

加载更多

window下安装maven

1.下载软件包: 2.解压到当前的安装路径: D:\Maven3.5.3 3.添加环境变量: 新建一个名为:MAVEN_HOME 填写解压路径:D:\Maven3.5.3 打开path,添加:%MAVEN_HOME%\bin 确定即可。 4.验证环境...

狼王黄师傅
7分钟前
0
0
聊聊flink的FsCheckpointStorage

序 本文主要研究一下flink的FsCheckpointStorage CheckpointStorage flink-runtime_2.11-1.7.0-sources.jar!/org/apache/flink/runtime/state/CheckpointStorage.java /** * CheckpointStor......

go4it
29分钟前
2
0
makefile 常用函数

Linux 环境下的程序员如果不会使用GNU make来构建和管理自己的工程,应该不能算是一个合格的专业程序员,至少不能称得上是 Unix程序员。今天我们来学习下makefile的常用函数。 《GNU make》h...

科陆李明
今天
17
0
Android 报错 Could not find com.android.tools.build:aapt2:3.2.1-4818971.

报错信息: Could not find com.android.tools.build:aapt2:3.2.1-4818971.Searched in the following locations: file:/C:/Users/96110/AppData/Local/Android/Sdk/extras/m2reposito......

lanyu96
今天
9
0
我的Linux系统九阴真经

我的Linux系统九阴真经 在今天,互联网的迅猛发展,科技技术也日新月异,各种编程技术也如雨后春笋一样,冒出尖来了。各种创业公司也百花齐放百家争鸣,特别是针对服务行业,新型互联网服务行...

linuxCool
今天
34
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部