正文 

当前位置： 首页 > java > java教程

算法（第4版）-2.2归并排序

Guure Guure     2022-08-14     640

关键词：

归并：将两个有序的数组归并成一个更大的有序数组。

 

归并算法：先（递归地）将它分为两半分别排序，然后将结果归并起来。

· 优点：保证将任意长度为N的数组排序所需时间和NlogN成正比；

· 缺点：所需的额外空间和N成正比。

 

 

2.2.1 原地归并的抽象方法

    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        // 将a[lo..mid]和a[mid+1..hi]归并
        int i = lo, j = mid + 1;

        for (int k = lo; k <= hi; k++) {    // 将a[lo..hi]复制到aux[lo..hi]
            aux[k] = a[k];
        }

        for (int k = lo; k <= hi; k++) {
            if (i > mid)                                        a[k] = aux[j++];    // 左半边用尽
            else if (j > hi)                                a[k] = aux[i++];    // 右半边用尽
            else if (less(aux[j], aux[i]))    a[k] = aux[j++];    // 右 < 左
            else                                                        a[k] = aux[i++];    // 右 > 左
        }
    }
merge

 

 

2.2.2 自顶向下的归并排序

public class Merge {
    private static Comparable[] aux;    // 归并所需的辅助数组

    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];    // 一次性分配空间
        sort(a, 0, a.length - 1);
    }


    private static void sort(Comparable[] a, int lo, int hi) {
        // 将数组a[lo..hi]排序
        if (hi <= lo)    return;
        int mid = lo + (hi - lo) / 2;
        sort(a, lo, mid);                // 将左半边排序
        sort(a, mid + 1, hi);        // 将右半边排序
        merge(a, lo, mid, hi);    // 归并结果
    }

    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        // 将a[lo..mid]和a[mid+1..hi]归并
        int i = lo, j = mid + 1;

        for (int k = lo; k <= hi; k++) {    // 将a[lo..hi]复制到aux[lo..hi]
            aux[k] = a[k];
        }

        for (int k = lo; k <= hi; k++) {
            if (i > mid)                                        a[k] = aux[j++];    // 左半边用尽
            else if (j > hi)                                a[k] = aux[i++];    // 右半边用尽
            else if (less(aux[j], aux[i]))    a[k] = aux[j++];    // 右 < 左
            else                                                        a[k] = aux[i++];    // 右 > 左
        }
    }

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private static void show(Comparable[] a) {
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++)
            StdOut.print(a[i] + " ");
        StdOut.println();
    }

    public static boolean isSorted(Comparable[] a) {
        // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1]))    return false;
        return true;
    }

    public static void main(String[] args) {
        // 从标准输入读取字符串，将它们排序并输出
        String[] a = In.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}
Merge

 

1. sort()方法的作用其实在于安排多次merge()方法调用的正确顺序。

 

2. 对于长度为N的任意数组，自顶向下的归并排序需要1/2NlgN至NlgN次比较，最多需要访问数组6NlgN次。

 

3. 通过以下方式我们还可能大幅度缩短归并排序的运行时间：

· 对小规模子数组使用插入排序

· 测试数组是否已经有序

· 不将元素复制到辅助数组

 

 

2.2.3 自底向上的归并排序

import java.lang.Math;

public class MergeBU {
    private static Comparable[] aux;    // 归并所需的辅助数组

    public static void sort(Comparable[] a) {
        // 进行lgN次两两归并
        int N = a.length;
        aux = new Comparable[N];
        for (int sz = 1; sz < N; sz = sz + sz)
            for (int lo = 0; lo < N - sz; lo += sz +sz)
                merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
    }

    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        // 将a[lo..mid]和a[mid+1..hi]归并
        int i = lo, j = mid + 1;

        for (int k = lo; k <= hi; k++) {    // 将a[lo..hi]复制到aux[lo..hi]
            aux[k] = a[k];
        }

        for (int k = lo; k <= hi; k++) {
            if (i > mid)                                        a[k] = aux[j++];    // 左半边用尽
            else if (j > hi)                                a[k] = aux[i++];    // 右半边用尽
            else if (less(aux[j], aux[i]))    a[k] = aux[j++];    // 右 < 左
            else                                                        a[k] = aux[i++];    // 右 > 左
        }
    }

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private static void show(Comparable[] a) {
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++)
            StdOut.print(a[i] + " ");
        StdOut.println();
    }

    public static boolean isSorted(Comparable[] a) {
        // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1]))    return false;
        return true;
    }

    public static void main(String[] args) {
        // 从标准输入读取字符串，将它们排序并输出
        String[] a = In.readStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}
MergeBU

 

1. 首先我们进行的是两两归并（把每个元素想象成一个大小为1的数组），然后是四四归并（将两个大小为2的数组归并成一个有4个元素的数组），然后是八八的归并，一直下去。在每一轮归并中，最后一次归并的第二个子数组可能比第一个子数组要小（但这对merge()方法不是问题），如果不是的话所有的归并中两个数组大小都应该一样，而在下一轮中子数组的大小会翻倍。

 

2. 对于长度为N的任意数组，自底向上的归并排序需要1/2NlgN至NlgN次比较，最多需要访问数组6NlgN次。

· 当数组长度为2的幂时，自顶向下和自底向上的归并排序所用的比较次数和数组访问次数正好相同，只是顺序不同；

· 其他时候，两种方法的比较和数组访问的次序会有所不同。

 

3. 自底向上的归并排序比较适合用链表组织的数据。

 

 

2.2.4 排序算法的复杂度

 

1. 没有任何基于比较的算法能够保证使用少于lg(N!)~NlgN次比较将长度为N的数组排序。

即最好情况至少是lg(N!)，最坏情况至少是NlgN。

 

2. 归并排序在最坏情况下的比较次数和任意基于比较的排序算法所需的最少比较次数都是~NlgN。

从零开始学习算法之归并排序[1]（2.2归并排序）

归并排序思想为将序列每相邻两个数字进行归并操作（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素重复步骤2，直到所有元素排序完毕。下列代码为... 查看详情

归并排序算法优化

1.什么是归并排序？更详细的解释可以百度，这里说说其主要思想：归并排序是采用分治思想，将所有的数均匀的分成n个等分的组，然后依次取(x,x+1)2个等分组，将他们合并排序，形成一个新的组，然后递归即可，最后会合并为... 查看详情

八大排序算法sumup，存干货，[建议收藏！！！](代码片段)

目录排序算法一、插入排序1.1直接插入排序1.2希尔排序二、选择排序2.1选择排序2.2堆排序三、交换排序3.1冒泡排序3.2快速排序3.2.1Hoare3.2.2前后指针法3.2.3挖坑法四、归并排序4.1递归版五、非递归排序5.1QuickSort非递归版5.2MergeSort非... 查看详情

数据结构和算法-排序算法-归并排序(代码片段)

...; 归并排序    #######################"""归并算法逻辑拆分对整个序列进行拆分，左边一部分，右边一部分然后对每一部分再次进行拆分，一直到拆分到只有一个元素，就到头了，第1次拆分：54,26,93,17,77,31,44,55,第2次... 查看详情

排序算法——归并排序

归并排序遵循分治原则先将数组不断的递归二分打散，打散后再进行二二组合。原理如下数组：分[1,2,3,4,5,6,7,8]分[1,2,3,4],[5,6,7,8]分[1,2],[3,4],[5,6],[7,8]分[1],[2],[3],[4],[5],[6],[7],[8]治：[2,1],[4,3],6,5],[8,7]治：[4,3,2,1],[8,7,6,5]治：[8,7,6,5,4,3,... 查看详情

数据结构-数组数组的相关算法(代码片段)

文章目录1无序数组的排序——快速排序1.1升序排序1.2降序排序2有序数组的查找——折半查找（二分查找）2.1升序数组的查找2.2降序数组的查找3有序数组的合并——归并思想3.1归并两个升序数组3.2归并两个降序数组3.3升... 查看详情

算法（第4版）-2.1初级排序算法

2.1.1游戏规则 1.排序成本模型：在研究排序算法时，我们需要计算比较和交换的数量。对于不交换元素的算法，我们会计算访问数组的次数。 2.·原地排序算法：除了函数调用所需的栈和固定数目的实例变量之外无需额外... 查看详情

算法(第4版)

第1章基础第2章排序第3章查找第4章图第5章字符串 第1章基础 第2章排序 第3章查找 第4章图 第5章字符串     ------------------------------------------------------------------------------------------ 查看详情

carson带你学数据结构：归并排序，稳定性最高的排序算法(代码片段)

目录1.简介属于内排序算法中的归并排序类别2.算法原理3.算法示意图4.算法实现有2种实现方式：递归&非递归方式4.1递归方式具体请看注释publicclassMergeSort/***归并排序算法实现*参数说明：*@paramarr=需排序的数组序... 查看详情

算法归并排序小和问题

....概述2.小和问题3.优化4.代码实现1.概述归并排序相关：【算法】归并排序这里参考视频：P32.认识O(NlogN)的排序2:29:0135分的时候视频。2.小和问题归并排序的扩展小和问题和逆序对问题在一个数组中，每一个数左边比当前数小的数... 查看详情

算法排序4：归并排序计数排序（非比较排序）(代码片段)

归并排序是建立在归并操作上的一种有效的排序算法，归并就是将已有序的子序列合并，得到完全有序的序列，归并排序的时间复杂度为O(N*logN)void_MergeSort(int*a,intbegin,intend,int*tmp) if(begin>=end) return; intmid=begin... 查看详情

经典排序算法-归并排序mergesort

经典排序算法-归并排序Mergesort原理,把原始数组分成若干子数组,对每个子数组进行排序,继续把子数组与子数组合并,合并后仍然有序,直到所有合并完,形成有序的数组举例无序数组[624159]先看一下每一个步骤下的状态,完了再看合... 查看详情

归并排序(代码片段)

目录1.概念2.自顶向下的归并排序算法（递归实现）2.1初实现2.2优化3.自底向上的归并排序(性能更优)3.1初实现3.2优化应用：求逆序对1.概念将一个数组排序，可以递归的将它们分成两半分别排序，然后将结果归并起来。体现了分... 查看详情

归并排序

...列；3.对子序列R[mid+1...high]递归，进行递归排序；4.调用算法merge合并两个子序列举例无序数组[624159]先看一下每个步骤下的状态,完了再看合并细节第一步[624159]原始状态第二步[26][14][59]两两合并排序,排序细节后边介绍第三步[1246] 查看详情

算法（第4版）-2.3快速排序

publicclassQuick{publicstaticvoidsort(Comparable[]a){StdRandom.shuffle(a);//消除对输入的依赖sort(a,0,a.length-1);}privatestaticvoidsort(Comparable[]a,intlo,inthi){if(hi<=lo)return;intj=partition(a,lo,hi);/ 查看详情

《算法零基础100例》(第39例)进阶排序-归并排序

...正在陆续实现中，11月正式推出，请稍作等待。《算法零基础100例》真正的零基础文章目录一、概念定义二、题目描述三、算法详解四、源码剖析五、推荐专栏六、粉丝福利一、概念定义二、题目描述三、算法详解四、源... 查看详情

排序算法——归并排序(代码片段)

算法思想归并排序的主要思想就是将一个待排序列，①不断地一分为二划分成一个元素组成序列，一个元素组成的序列也就是有序序列，②然后再合并将相邻的两个有序序列，最终待排序列变成一个有序序列。总之，归并算法就... 查看详情

直通bat算法精讲附程序源码

...转练习题免费第2章排序4视频|16练习详细介绍常见的排序算法过程，以及各个排序算法稳定性、时间和空间复杂度，当然还有常见面试题目的讲解。2.1排序(1)2.2冒泡排序练习题2.3选择排序练习题2.4插入排序练习题2.5归并排序练习... 查看详情