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

    2021-02-21 10:41:53
    一、概念 来自百度百科 归并排序(Merge Sort)是建立在归并操作上的一种有效...改进归并排序在归并时先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。如果前段序列的最大值小于等于后段序列最小

    一、概念

    来自百度百科

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

    二、时间复杂度

    归并排序比较占用内存,但却是一种效率高且稳定的算法。
    改进归并排序在归并时先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。如果前段序列的最大值小于等于后段序列最小值,则说明序列可以直接形成一段有序序列不需要再归并,反之则需要。所以在序列本身有序的情况下时间复杂度可以降至O(n)

    三、过程动态演示

    归并排序

    四、Java源代码实现

    import java.util.Arrays;
    
    public class MergeSort {
        public static void merge(int a[],int left, int mid, int right){
            // 保存一份副本b,修改时则将对应内容复制到数组a中
            int b[] = Arrays.copyOfRange(a,left,right+1);
            int l = left,r = mid+1;//l左边部分索引,r是右边部分索引
            for(int k = left; k<=right;k++){
                //左边部分处理完毕
                if(l>mid){
                    a[k] = b[r-left];
                    r++;
                }else if(r>right){
                    //右边部分处理完毕
                    a[k] = b[l-left];
                    l++;
                }else if(b[l-left]<b[r-left]){
                    // 左半部分所指元素 < 右半部分所指元素
                    a[k] = b[l-left];
                    l++;
                }else {// 左半部分所指元素 >= 右半部分所指元素
                    a[k] = b[r-left];
                    r++;
                }
            }
    
        }
        private static void sort(int a[],int left,int right){
            //递归终止条件
            if(left>=right){
                return;
            }
            //取中间长度
            int mid = (left+right)/2;
            //左边
            sort(a,left,mid);
            //右边
            sort(a,mid+1,right);
            //归并
            if(a[mid]>a[mid+1]){
                merge(a,left,mid,right);
            }
        }
        //这个sort是对外接口
        public static void sort(int a[]){
            int len = a.length;
            sort(a,0,len-1);
        }
    
        public static void main(String[] args) {
            int a[]={36,14,35,34,50,29,16,8,17,15};
            sort(a);
            for(int i = 0;i<a.length;i++){
                System.out.print(a[i]+",");
            }
        }
    }
    

    想了解具体工作过程的可以在idea在merge函数打断点进行调试,你会发现跟上面的过程是一样的。

    展开全文
  • java归并排序

    2019-07-13 12:14:24
    归并排序 稳定性:稳定 归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部...

    归并排序 稳定性:稳定


    归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。

     

    归并排序


    基本思想


    归并排序就是利用归并的思想实现的排序方法。而且充分利用了完全二叉树的深度是的特性,因此效率比较高。其基本原理如下:对于给定的一组记录,利用递归与分治技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归方法将排好序的半子表合并成为越来越大的有序序列。 

    经过第一轮比较后得到最小的记录,然后将该记录的位置与第一个记录的位置交换;接着对不包括第一个记录以外的其他记录进行第二次比较,得到最小记录并与第二个位置记录交换;重复该过程,知道进行比较的记录只剩下一个为止。

    工作原理:

    (1)申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 

    (2)设定两个指针,最初位置分别为两个已经排序序列的起始位置 

    (3)比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 

    (4)重复步骤3直到某一指针达到序列尾 

    (5)将另一序列剩下的所有元素直接复制到合并序列尾

    算法分析
    一趟归并需要将数组 a[]中相邻的长度为h的有序序列进行两两归并.并将结果放到temp[]中,这需要将待排序列中的所有记录扫描一遍,因此耗费O(n),而又完全二叉树的深度可知,整个归并排序需要进行()次,因此总的时间复杂度为O(nlogn),而且这是归并排序算法中最好、最坏、平均的时间性能。

    由于归并排序在归并过程中需要与原始序列同样数量的存储空间存放归并结果以及递归时深度为的栈空间,因此空间复杂度为O(n+logn).

    另外,对代码进行仔细研究,发现merge函数中有if (a[i] < a[j]) 的语句,说明它需要两两比较,不存在跳跃,因此归并排序是一种稳定的排序算法。

    也就是说,归并排序是一种比较占内存,但却效率高且稳定的算法。Java实现

    /**
    
     * 归并排序
    
     * @param data
    
     * @param low
    
     * @param mid
    
     * @param high
    
     */
    
    public static voidmerge(int[] data, int low, int mid, int high) {
    
        int[] temp = new int[high - low + 1];
    
        int i= low;// 左指针
    
        int j = mid + 1;// 右指针
    
        int k = 0;
    
        // 把较小的数先移到新数组中
    
        while (i <= mid && j <= high){
    
            if (data[i] < data[j]) {
    
                temp[k++] = data[i++];
    
            } else {
    
                temp[k++] = data[j++];
    
            }
    
        }
    
        // 把左边剩余的数移入数组
    
        while (i <= mid) {
    
            temp[k++] = data[i++];
    
        }
    
        // 把右边边剩余的数移入数组
    
        while (j <= high) {
    
            temp[k++] = data[j++];
    
        }
    
        // 把新数组中的数覆盖nums数组
    
        for (int k2 = 0; k2 < temp.length; k2++){
    
            data[k2 + low] = temp[k2];
    
        }
    
    }
    
    /**
    
     * 归并排序
    
     * 时间复杂度:O(nlog2n)
    
     * @param data
    
     * @param low
    
     * @param high
    
     */
    
    public static voidmergeSort(int[] data, int low, int high) {
    
        int mid = (low + high) / 2;
    
        if (low < high) {
    
            mergeSort(data, low, mid);//左边
    
            mergeSort(data, mid + 1, high);//右边
    
            merge(data, low, mid, high);//左右归并
    
        }
    
    }


     

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

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

      1.最好时间复杂度、最坏时间复杂度、平均时间复杂度

      2.是否是原地排序算法:原地排序算法,指空间复杂度为O(1)

      3.是否是稳定排序算法:稳定排序算法,指如果待排序序列中有值相等的元素,经过排序之后,值相等元素的顺序保持不变

      关于归并排序:

    #综述:
        1.冒泡排序、插入排序、选择排序算法的时间复杂度都是O(n^2)。只适合小规模数据的排序
        2.归并排序、快速排序算法的时间复杂度是O(nlogn)。适合大规模数据的排序
        3.归并排序、快速排序算法都应用了分治思想
        
    #描述归并排序:
        归并排序的核心思想,就是分而治之。比如要排序一个数组,先把数据从中间分成前后两个部分,然后对前后两部分分别排序,再将排好序的两部分进行合并。最终整个数组就排好序了。
        
    #实现公式:
        地推公式:
            merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
    
        终止条件:
            p >= r 不用再继续分解

     

      代码实现:

    package com.anan.algorithm;
    
    import java.util.Arrays;
    
    /**
     * 归并排序
     */
    public class MergeSort {
    
        public static void main(String[] args) {
            int[] a={4,5,6,3,2,1,8,9,12,11,8};
            System.out.println("排序前:"+ Arrays.toString(a));
    
            // 排序
            mergeSort(a,0,a.length-1);
    
            System.out.println("排序后:"+Arrays.toString(a));
        }
    
        // 第一步:拆分
        public static void mergeSort(int[] a,int left,int right){
            // 递归终止条件
            if(left>=right)return ;
    
            // 计算中间位置
            int mid = (left+right)/2;
            // 中间位置向左方向,左边继续拆分
            mergeSort(a,left,mid);
            // 中间位置向右方向,右边继续拆分
            mergeSort(a,mid+1,right);
    
            // 合并的过程
            merge(a,left,mid+1,right);
        }
    
        // 第二步:合并
        /**
         *  参数:
         *      a:数组
         *      left:指向数组第一个元素
         *      mid:指向数组分割元素
         *      right:指向数组最后一个元素
         */
        public static void merge(int[] a,int left,int mid,int right){
            // 左边数组大小
            int[] leftA = new int[mid-left];
            // 右边数组大小
            int[] rightA = new int[right-mid+1];
    
            // 左边数组填充数据
            for(int i=left;i<mid;i++){
                leftA[i-left]=a[i];
            }
    
            // 右边数组填充数据
            for(int j=mid;j<=right;j++){
                rightA[j-mid]=a[j];
            }
    
            // 定义两个位置指针
            int L_INDEX=0,R_INDEX=0;
            // a数组第一个元素位置
            int k=left;
    
            // 比较两个数组的值,将小的一个放入数组a中
            while(L_INDEX<leftA.length && R_INDEX<rightA.length){
                // 谁比较小,谁将元素放入大数组中,移动指针,继续比较下一个
                if(leftA[L_INDEX] < rightA[R_INDEX]){
                    a[k]=leftA[L_INDEX];
    
                    // 移动位置
                    L_INDEX++;
                    k++;
                }else{
                    a[k] = rightA[R_INDEX];
    
                    // 移动位置
                    R_INDEX++;
                    k++;
                }
    
            }
    
            // 如果左边的数组还没有比较完成。右边的数组已经比较完成。则将左边余下的数直接放入大数组a中
            while(L_INDEX<leftA.length){
                a[k] = leftA[L_INDEX];
    
                // 移动位置
                L_INDEX++;
                k++;
            }
    
            // 如果右边的数组还没有比较完成。左边的数组已经比较完成。则将右边余下的数直接放入大数组a中
            while(R_INDEX<rightA.length){
                a[k] = rightA[R_INDEX];
    
                // 移动位置
                R_INDEX++;
                k++;
            }
    
        }
    }

     

      

    转载于:https://www.cnblogs.com/itall/p/11137739.html

    展开全文
  • 归并排序算法详解

    2020-05-27 13:58:56
    改进归并排序在归并时先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。如果前段序列的最大值小于等于后段序列最小值,则说明序列可以直接形成一段有序序列不需要再归并,反之则需要。所以在...

    归并排序算法

    通识:归并排序首先就会将当前数组分解为左右两部分,之后左右两部分又分别再继续分为左右两部分,说到这里大家肯定就能想起递归了,是的,直到分解为当前各个部分只有一个数值为止,之后将配对的左右部分按照大小合并为一个新的数组,比如下图所示。
    在这里插入图片描述
    归并排序比较占用内存,但却是一种效率高且稳定的算法。
    改进归并排序在归并时先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。如果前段序列的最大值小于等于后段序列最小值,则说明序列可以直接形成一段有序序列不需要再归并,反之则需要。所以在序列本身有序的情况下时间复杂度可以降至O(n)
    下面示例代码使用的是未优化的:
    下面展示一些 内联代码片

    public class merge_sort {
        public static int [] mergesort(int a[],int left,int right){
            if (left==right)
            {
                return new int []{a[left]};
            }
            int mid=(left+right)/2;//找到将数组划分为两部分的数值(中位数,平均值)
            int []leftarr=mergesort(a,left,mid);//划分为左部分
            int [] rightarr=mergesort(a,mid+1,right);//划分为右部分
            int [] newarr=new int[leftarr.length+rightarr.length];//开辟一个新数组,长度为左右两个数组长度的总和,用来容纳两个数组的值
            int m=0,n=0,length=0;
            for (int i=0;i<leftarr.length+rightarr.length;i++)//左右两个数组进行比较,依次从小到大将数值放入新的数组中
            {
                if(m>=leftarr.length)//如果leftarr(左部数组)遍历完了,那么直接将右部数组剩余值放入新数组(newarr)中
                {
                    newarr[length++]=rightarr[n++];
                }
                else if(n>=rightarr.length)//如果rightarr(右部数组)遍历完了,那么直接将左部数组剩余值放入新数组(newarr)中
                {
                    newarr[length++]=leftarr[m++];
                }
                else if(leftarr[m]<=rightarr[n])//如果左部数组当前值小于等于右部分数组当前值,则将左部数组当前值放入新数组(newarr)中
                {
                    newarr[length++]=leftarr[m++];
                }
                else//否则将右部数组当前值放入新数组(newarr)中
                {
                    newarr[length++]=rightarr[n++];
                }
            }
            return newarr;
        }
        public static void main(String [] args){
            int [] numbers={8,2,5,3,9,4,6,7,1,7};
            int [] new_numbers=mergesort(numbers,0,numbers.length-1);
            for(int i=0;i<new_numbers.length;i++)
            {
                System.out.print(new_numbers[i]+" ");
            }
    
        }
    }
    
    展开全文
  • 数据结构-排序-归并排序 1.算法思想 归并排序的思想: 2.算法复杂度 执行时间: 附加空间: 是否稳定的排序方法: 3.算法实现 运行截图 欢迎大家关注我的博客:breeziness123 转载说明出处 ...
  • 定义归并就是将两个或多个有序的序列合并成一个有序序列的过程。二路归并排序是面试中考查最多的排序算法之一。归并排序有两种: 1、一般归并排序,空间复杂度O(n) 2、原地归并排序,空间...是否稳定:是举例说明
  • 文章目录比较三种排序方法一、选择排序二、冒泡排序...是否稳定 归并排序(Merge Sort) O(nlogn)O(nlogn) O(nlogn) O(n2)O(n^{2}) O(n2) T(1)T(1) T(1) 否 快速排序(Quick Sort) O(nlogn)O(nlogn) O(nlogn)...
  • 是否稳定的排序算法2.时间复杂度如何分析递归代码的时间复杂度3.空间复杂度 归并排序 原理/核心思想: 如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并...
  • 排序算法之归并排序

    2017-05-29 16:04:33
    归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个...
  • 排序算法-归并排序

    2014-10-13 13:04:51
    对排序算法的分类一般按照以下几点: 1. 按排序是否稳定,即
  • 归并排序是一个相对稳定的排序,python排序的底层实践就是使用的归并排序 实现代码 """ dateTime: 2021-05-01 19:40 sort: merge time: O(nlog2n) space: O(n) """ def merge_sort(array, left, right): """ ...
  • 那么已经非常高效的归并排序是否还能再优化呢?当然是可以的,timsort就是在归并排序上改进的一种高级排序方式,现在广泛运用在如python,Java等主流语言中。timsort是高效的,完整的算法是相当复杂的,因此我这里...
  • 稳定排序:冒泡、插入、归并、基数 不稳定排序:希尔、选择、堆排序、快速排序 0.3稳定性分析: 0.1冒泡:比较相邻位置的元素,比较大小然后选择是否交换,如果相等不会做处理,所以如果两个数相等,排序后他们...
  • 起泡排序 ...初始版本时间复杂度O(n^2)。 改进:考虑到向量中的前段和后段是不是已经是有序的。...算法是否稳定归并排序 https://www.bilibili.com/video/av18980253/ 时间复杂度O(nlogn)。...
  • 目录整体记忆快速排序堆排序建堆时间复杂度推导建堆删除插入堆排序归并排序冒泡排序直接插入排序简单选择排序希尔排序整体记忆名称时间复杂度何时最差是否稳定快速排序平均O(nlogn),最坏O(n^2),最好O(nlogn)数...
  • 归并排序算法(C语言)

    千次阅读 2018-04-11 14:03:10
    归并排序: 利用将两个的有序数据序列合并成一个新的有序数据序列,在如何分成两个有序数据的问题下,采用分治算法。 时间复杂度:O(n*logn) 空间复杂度:O(n) 是否稳定: 稳定
  • 选择排序(每次选出未排序最小的和未排序首位置交换)、 快速排序(随机选取一个值为基准,把基准放到最前面或者最后面,这就决定你排序开始的位置是从前往后还是...冒泡排序、插入排序、归并排序(虽然和快排都是...
  • 归并排序  归并排序归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。...
  • 内部排序,外部排序 ...一、归并排序 递归实现 - > 自上向下 非递归排序 - > 自下向上 时间复杂度:O(NlogN)O(NlogN)O(NlogN) 先分再合 /* 将序列对半拆分直到序列长度为1*/ void MergeSort_UptoDo
  • 算法原理 ...归并算法是否稳定,关键在于merge函数合并时的代码。在合并过程冲如果A[p, q]和A[q+1, r]中有值相同的元素,将A[p, q]中的元素放在temp前面,就可以保证算法的稳定性。 时间复杂度 .
  • 冒泡排序法:相邻比较大小,来决定是否交换位置,依次迭代,标准的冒泡排序内循环是在尾部开始的;稳定 插入排序法:打扑克牌整理牌时的做法,注意需要用到temp来缓存下一个值;稳定; 选择排序法:冒泡太着急了,...
  • 目录2-路归并排序 2-way Merge Sort排序过程思路将两个有序子序列归并成一个有序子序列递归实现非递归实现算法实现算法评价T(n)S(n)是否稳定总结 归并:将两个或两个以上的有序表组合成一个新的有序表 通过归并两个...
  • 上期为大家讲解了排序算法常见的几个概念:相关性:排序是否需要比较元素稳定性:相同元素排序是否可能打乱时间空间复杂度:随着元素增加时间和空间随之变化的函数如果有遗忘的同学可以看排序算法——(1)简介这...
  • offer必备三大算法之一——归并排序 平均时间复杂度:O(nlogn)稳定性:稳定 分两步:递归(递归的调用排序函数,将原始数组递归的一分为二,分裂为n个单独的元素,单独即有序)——归并(合并两个已排序的序列) ...
  • 归并排序-by-Python

    2019-02-01 13:26:47
    是否稳定排序:Yes 是否是原地排序:No python 实现: class Solution: def mergeSort(self, nums): """ :type nums: List[int] :rtype: List[int] """ l...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 225
精华内容 90
关键字:

归并排序是否稳定