精华内容
下载资源
问答
  • Java 归并排序算法

    2020-12-23 18:12:30
    上一章我们学习了 Java 快速排序算法,这一章,我们来学习快归并排序算法,so,多了不说,继续老规矩,学习内容如下: 1、归并排序的定义 2、归并排序的思路 3、代码实现 4、运行过程 & 代码分析 1、归并排序的...

    简介

    上一章我们学习了 Java 快速排序算法,这一章,我们来学习快归并排序算法,so,多了不说,继续老规矩,学习内容如下:
    1、归并排序的定义
    2、归并排序的思路
    3、代码实现
    4、运行过程 & 代码分析

    1、归并排序的定义

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

    和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(n log n)的时间复杂度。代价是需要额外的内存空间。

    2、归并排序的思路

    • 把长度为n的输入序列分成两个长度为n/2的子序列;
    • 对这两个子序列分别采用归并排序;
    • 将两个排序好的子序列合并成一个最终的排序序列。

    这里借助一个图 此图为借鉴,自己懒得画,如有侵权,请联系我处理! 作为说明:假设数组源为,84571362
    在这里插入图片描述

    3、代码实现

    package com.gongchao.boss;
    
    import java.util.Arrays;
    
    /**
     * description: 归并排序方法
     * auth: zengtao
     * time: 2020-12-23 16:45
     **/
    public class Main {
    
        public static void main(String[] args) {
            int array[] = {6, 5, 2, 7, 4, 3, 8, 12, 4, 9};
            // 归并排序方法
            System.out.println("排序前:" + Arrays.toString(array));
            mergeSoft(array, 0, array.length - 1);
            System.out.println("排序后:" + Arrays.toString(array));
        }
    
        // 归并
        private static void mergeSoft(int[] arr, int low, int high) {
            int middle = (high + low) / 2;
            //递归,直到low==high,也就是数组已不能再分了,
            if (low < high) {
                // 左数组排序
                mergeSoft(arr, low, middle);
                // 右数组排序
                mergeSoft(arr, middle + 1, high);
                // 当数组不能再分,开始归并排序
                merge(arr, low, middle, high);
            }
        }
    
        /**
         * 合并数据
         *
         * @param arr    数组
         * @param low    开始位置
         * @param middle 中间位置
         * @param high   结束位置
         */
        private static void merge(int[] arr, int low, int middle, int high) {
            // 临时数组,用于存储arr数据
            int[] tempArr = new int[high - low + 1];
            // 第一个数组的开始下标
            int i = low;
            // 第二个数组的开始下标
            int j = middle + 1;
            // 临时数组的下标,默认为0开始
            int index = 0;
    
            // 比较两个数组中的数据,然后存储
            while (i <= middle && j <= high) {
                // 两个数组第一个数据比较,把小的数组放入数组中,临时数组下标和数组小/大的下标移动
                if (arr[i] <= arr[j]) {
                    tempArr[index++] = arr[i++];
                } else {
                    tempArr[index++] = arr[j++];
                }
            }
    
            // 上面数据对比之后,数据1数据还有剩余
            // 数组1【6, 5, 2, 7, 4, 3, 8】,数组2【12, 4, 9】,那么,数组1数据>数组2数据,
            if (i <= middle) {
                // 只剩数组1数据,都是有序数据,所以数据直接放入临时数组
                tempArr[index++] = arr[i++];
            }
            // 上面数据对比之后,数据2数据还有剩余
            // 数组1【6, 5, 2, 7】,数组2【4, 3, 8,12, 4, 9】,那么,数组1数据< 数组2数据,
            if (j <= high) {
                // 只剩数组2数据,都是有序数据,所以数据直接放入临时数组
                tempArr[index++] = arr[j++];
            }
    
            System.out.println("    排序中:" + Arrays.toString(arr));
    
            // 重新临时数组中的数据,放入原数组中
            for (int k = 0; k < index; k++) {
                arr[k + low] = tempArr[k];
            }
        }
    }
    

    运行结果
    在这里插入图片描述
    根据运行结果:这样我们就是实现了归并排序

    4、运行过程 & 代码分析

    为什么要写这个呢?

    之前有些同学私信我,有些局部代码看起来还是有些吃力,感觉自己便携代码有点抓不住。

    所以,这个也是针对这些同学,我一点一点的说明,方便同学更加方便理解。

    一:首先我们先按照排序的思路来看

    把长度为n的输入序列分成两个长度为n/2的子序列;
    对这两个子序列分别采用归并排序;

    分析

    • 长度为n的输入序列------> 输入数组arr[]
    • 输入数组,分为长度为n/2的数组------> 第1⃣️个开始位置到结束,第2⃣️个开始位置(第一个结束位置)到整个数组结束
    • 对这两个子序列分别采用归并排序 -----> 方法中有归并,第1⃣️个归并,第2⃣️个归并

    那么方法和参数就如约而来了,代码如下:

    	// 归并
        private static void mergeSoft(int[] arr, int low, int high) {
            int middle = (high + low) / 2;
            //递归,直到low==high,也就是数组已不能再分了,
            if (low < high) {
                // 左数组排序
                mergeSoft(arr, low, middle);
                // 右数组排序
                mergeSoft(arr, middle + 1, high);
                // 当数组不能再分,开始归并排序
                merge(arr, low, middle, high);
            }
        }
    

    二:其次我们看最后一个思路

    将两个排序好的子序列,合并成一个最终的排序序列。

    那么就会有一个最终的具体的合并排序方法,内部原理如下

    • 1.将数组分类2个,那么分别有2个,各自的start位置+结束位置
     private static void merge(int[] arr, int low, int middle, int high) {
     
     }
    
    • 2.分别将2个数组对比,大数组的放在一边,小的数据放在一边
    		// 临时数组,用于存储arr数据
            int[] tempArr = new int[high - low + 1];
            // 第一个数组的开始下标
            int i = low;
            // 第二个数组的开始下标
            int j = middle + 1;
            // 临时数组的下标,默认为0开始
            int index = 0;
    
            // 比较两个数组中的数据,然后存储
            while (i <= middle && j <= high) {
                // 两个数组第一个数据比较,把小的数组放入数组中,临时数组下标和数组小/大的下标移动
                if (arr[i] <= arr[j]) {
                    tempArr[index++] = arr[i++];
                } else {
                    tempArr[index++] = arr[j++];
                }
            }
    
    • 3.若:数组1vs数组2,数组1数据多,那么继续处理数组1,此为有序排序,若:数组1vs数组2,数组2多,那么继续处理数组2
            // 上面数据对比之后,数据1数据还有剩余
            // 数组1【6, 5, 2, 7, 4, 3, 8】,数组2【12, 4, 9】,那么,数组1数据>数组2数据,
            if (i <= middle) {
                // 只剩数组1数据,都是有序数据,所以数据直接放入临时数组
                tempArr[index++] = arr[i++];
            }
            // 上面数据对比之后,数据2数据还有剩余
            // 数组1【6, 5, 2, 7】,数组2【4, 3, 8,12, 4, 9】,那么,数组1数据< 数组2数据,
            if (j <= high) {
                // 只剩数组2数据,都是有序数据,所以数据直接放入临时数组
                tempArr[index++] = arr[j++];
            }
    
    • 4.将最终数据返回给原数组
     // 重新临时数组中的数据,放入原数组中
            for (int k = 0; k < index; k++) {
                arr[k + low] = tempArr[k];
            }
    

    到此为止

    代码具体解析,都已一一说明,希望对同学们有用。

    谢谢观看,Thanks!

    展开全文
  • 主要简单介绍了java 归并排序算法的工作原理及代码,需要的朋友可以参考下
  • 主要介绍了Java 归并排序算法、堆排序算法实例详解,需要的朋友可以参考下
  • java归并排序算法

    2021-05-14 15:55:03
    归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段...

    归并排序

    归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
    排序过程

    1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
    2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
    3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
    4. 重复步骤 3 直到某一指针到达序列尾
    5. 将另一序列剩下的所有元素直接复制到合并序列尾
      在这里插入图片描述
    import java.util.Arrays;
    
    public class MergeSort {
    
        public static void mergeSort(int[] arrays, int left, int right) {
                    // 如果数组还可以拆分
            if (left < right) {
                //数组的中间位置
                int middle = (left + right) / 2;
                //拆分左边数组
                mergeSort(arrays, left, middle);
                //拆分右边数组
                mergeSort(arrays, middle + 1, right);
                //合并
                merge(arrays, left, middle, right);
            }
        }
    
    
        /**
         * 合并数组
         */
        public static void merge(int[] arr, int left, int middle, int right) {
            //申请合并空间 大小为两个已经排序序列之和
            int[] temp = new int[right - left + 1];
            //i 和 j为两个已经排好序的数组的起始位置
            int i = left;
            int j = middle + 1;
            int k = 0;
            //排序
            while (i <= middle && j <= right) {
                //将比较小的数组放入合并空间
                if (arr[i] < arr[j]) {
                    temp[k++] = arr[i++];
                } else {
                    temp[k++] = arr[j++];
                }
            }
            //将左边剩余元素写入合并空间
            while (i <= middle) {
                temp[k++] = arr[i++];
            }
            //将右边剩余的元素写入合并空间
            while (j <= right) {
                temp[k++] = arr[j++];
            }
            //将排序后的数组写回原来的数组
            for (int l = 0; l < temp.length; l++) {
                arr[l + left] = temp[l];
            }
    
        }
    
        public static void main(String[] args) {
            int[] ints = {5, 3, 4, 1, 2};
            mergeSort(ints,0,ints.length-1);
            System.out.println(Arrays.toString(ints));
        }
    }
    
    展开全文
  • Java归并排序算法

    2017-03-13 21:28:08
    归并排序-层级log(N)-归并过程时间复杂度O(N) -需要额外的O(N)空间 以空间换时间 -总时间复杂度O(Nlog(N))具体实现public class MergeSort { // 归并排序 public static ...

    归并排序

    -层级log(N)

    这里写图片描述

    -归并过程时间复杂度O(N)
    这里写图片描述
    -需要额外的O(N)空间

    以空间换时间

    -总时间复杂度O(Nlog(N))

    具体实现

    public class MergeSort {
    
        // 归并排序
        public static <T extends Comparable<? super T>> void MergeSort(T[] arr, int n) {
            sonOfMergeSort(arr, 0, n - 1);
        }
    
        // 递归使用归并排序,对arr[l...r]的范围进行排序
        private static <T extends Comparable<? super T>> void sonOfMergeSort(T[] arr, int l, int r) {
            // if (l >= r) {
            // return;
            // }
            // 当n小到一定程度时,插入排序比归并排序快
            if (r - l <= 15) {
                // 当分块中元素为15+1时,换成插入排序
                SelectionSort.insertionSort(arr,r,l);
                return;
            }
            int mid = (l + r) / 2;
            sonOfMergeSort(arr, l, mid);
            sonOfMergeSort(arr, mid + 1, r);
            // 若满足if则序列为有序的,对近乎有序的数组会起到优化作用
            if (arr[mid].compareTo(arr[mid + 1]) > 0) {
                merge(arr, l, mid, r);
            }
        }
    
        // 将arr[l...mid]和arr[mid+l..r]两部分进行归并
        public static <T extends Comparable<? super T>> void merge(T[] arr, int l, int mid, int r) {
            T[] aux = arr.clone();
            for (int i = l; i <= r; i++)
                aux[i - l] = arr[i];
            int i = l, j = mid + 1;
            for (int k = l; k <= r; k++) {
                if (i > mid) {
                    arr[k] = aux[j - l];
                    j++;
                } else if (j > r) {
                    arr[k] = aux[i - l];
                    i++;
                } else if (aux[i - l].compareTo(aux[j - l]) < 0) {
                    arr[k] = aux[i - l];
                    i++;
                } else {
                    arr[k] = aux[j - l];
                    j++;
                }
            }
        }
    
        // 自底向上的归并排序
        // 未使用数组索引,可以使用链表访问
        public static <T extends Comparable<? super T>> void mergeSortBU(T[] arr, int n) {
            for (int i = 1; i < n; i += i) {
                for (int j = 0; j + i < n; j += i + i) {
                    // 对arr[j..j+i-1]和对arr[j..j+i+i-1]进行归并,并对可能得越界问题进行处理
                    MergeSort.merge(arr, j, j + i - 1, Math.min(j + i + i - 1, n - 1));
                }
            }
        }
    }
    展开全文
  • 归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。两路归并算法1、算法基本思路设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R...

    归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。

    两路归并算法

    1、算法基本思路

    设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中。

    (1)合并过程

    合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字,取关键字较小的记录复制到R1[p]中,然后将被复制记录的指针i或j加1,以及指向复制位置的指针p加1。

    重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空),此时将另一非空的子文件中剩余记录依次复制到R1中即可。

    (2)动态申请R1

    实现时,R1是动态申请的,因为申请的空间可能很大,故须加入申请空间是否成功的处理。

    2、归并算法

    void Merge(SeqList R,int low,int m,int high)

    {//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的

    //子文件R[low..high]

    int i=low,j=m+1,p=0;//置初始值

    RecType *R1;//R1是局部向量,若p定义为此类型指针速度更快

    R1=(ReeType *)malloc((high-low+1)*sizeof(RecType));

    if(! R1) //申请空间失败

    Error("Insufficient memory available!");

    while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上

    R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];

    while(i<=m) //若第1个子文件非空,则复制剩余记录到R1中

    R1[p++]=R[i++];

    while(j<=high) //若第2个子文件非空,则复制剩余记录到R1中

    R1[p++]=R[j++];

    for(p=0,i=low;i<=high;p++,i++)

    R[i]=R1[p];//归并完成后将结果复制回R[low..high]

    } //Merge

    归并排序

    归并排序有两种实现方法:自底向上和自顶向下。

    展开全文
  • Java归并排序算法实现

    2016-09-01 09:46:23
    归并排序算法采用分治,将已有序的子集合并,以得到完全有序的集一:创建归并后的集result,其length等同于待归并的两子集length之和 二:创建三个指针,分别指向result集,待归并集ints1,待归并集ints2初始位置 三:...
  • 归并排序算法依赖归并操作。归并排序有多路归并排序、两路归并排序 , 可用于内排序,也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。 原理: 把 n 个记录看成 n 个长度为 l 的有序子表 进行两两归并使...
  • 主要介绍了java归并排序算法详解的相关资料,归并排序算法又称为合并排序算法,是一种时间复杂度为O(N logN)的排序算法,因而其在平常生活工作中应用非常广泛,需要的朋友可以参考下
  • 主要介绍了Java分治归并排序算法,结合实例形式详细分析了分治归并排序算法的原理及java实现技巧,需要的朋友可以参考下
  • java实现归并排序算法

    2020-09-02 21:27:24
    在学习算法的过程中,我们难免会接触很多和排序相关的算法。总而言之,对于任何编程人员来说,基本的排序算法是必须要掌握的。那么现在我们将要进行基本的归并排序算法的讲解
  • 归并排序算法一、归并排序的概念二、原地归并的抽象方法(一)、原地归并的抽象方法的概念(二)、原地归并的抽象方法的代码示例三、自顶向下的归并排序(一)、自顶向下的归并排序的概念(二)、自顶向下的归并排序...
  • 本文实例讲述了Java排序算法总结之归并排序。分享给大家供大家参考。具体分析如下:归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。和快速排序类似,让我们一起来看,归并在Java...
  • Java归并排序

    2020-10-08 18:47:26
    Java 实现归并排序
  • 主要为大家详细介绍了Java经典排序算法归并排序,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • java 归并排序

    2020-10-30 17:04:41
    java归并排序
  • java归并排序

    2020-08-14 20:50:06
    java归并排序 归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治策略,将大问题分治成一些小问题然后递归求解,治将分的阶段得到的答案修补在一起实现分而治之 归并排序具体图解如下 实例代码 ...
  • Java常用排序算法归并排序(二路归并排序

    千次阅读 多人点赞 2017-02-27 23:17:10
    归并排序 二路归并排序 Java实现
  • 主要介绍了Java排序算法总结之归并排序,较为详细的分析了归并排序的原理与java实现技巧,需要的朋友可以参考下
  • 必须知道的八大种排序算法【java实现】(三) 归并排序算法、堆排序算法详解 一、归并排序算法 基本思想:  归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子...
  • Java 归并排序

    2017-05-31 20:36:58
    归并排序
  • 归并排序算法的核心思想是要将两个有序数组归并为一个有序数组,再归并排序的初始时,是对两个分别有一个元素的数组(一个元素显然是有序的)进行归并 下边是时实现这个核心思想的java代码 // 在下边的方法中 其实...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 35,771
精华内容 14,308
关键字:

java归并排序算法

java 订阅