精华内容
下载资源
问答
  • 归并排序稳定的排序
    千次阅读
    2021-06-15 22:05:30

    归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要。归并排序的比较次数小于快速排序的比较次数,移动次数一般多于快速排序的移动次数。

    更多相关内容
  • 归并排序稳定性分析

    千次阅读 2021-05-29 10:38:51
    归并排序稳不稳定关键要看 merge() 函数,也就是两个有序子数组合并成一个有序数组的那部分代码。在合并的过程中,如果 A[p…m]和 A[m+1…r]之间有值相同的元素,那我们可以像伪代码中那样,先把 A[p…q]中的元素放...

    归并排序稳不稳定关键要看 merge() 函数,也就是两个有序子数组合并成一个有序数组的那部分代码。在合并的过程中,如果 A[p…m]和 A[m+1…r]之间有值相同的元素,那我们可以像伪代码中那样,先把 A[p…q]中的元素放入 tmp 数组。这样就保证了值相同的元素,在合并前后的先后顺序不变。所以,归并排序是一个稳定的排序算法

    def merge(lst1, lst2):  # 有序列表lst1 lst2 合并成lst3
        lst3 = []
        i1, i2 = 0, 0  # 追踪每个列表当前的位置
        n1, n2 = len(lst1), len(lst2)
        while i1 < n1 and i2 < n2:  # lst1 和lst2 都拥有更多元素
            if lst1[i1] < lst2[i2]:  # lst1 的第一个元素更小
                lst3.append(lst1[i1])  # 把这个小的追加到临时列表
                i1 = i1 + 1
            else:  # lst2 的第一个元素更小
                lst3.append(lst2[i2])
                i2 = i2 + 1
        if i1 == n1:
            for i in lst2[i2:]:
                lst3.append(i)
        else:
            for i in lst1[i1:]:
                lst3.append(i)
        return lst3
    
    
    def mergeSort(nums):
        n = len(nums)
        if n <= 1:
            return nums
        m = n // 2
        left = mergeSort(nums[:m])
        right = mergeSort(nums[m:])
        return merge(left, right)
    
    
    print(mergeSort([1, 3, 2, 4, 5, 7, 9,2]))
    
    

    总结

    • 先操作左半部分,再操作右半部分,归并排序就是稳定的
    展开全文
  • 1)归并排序的核心思想,先把arr的L--R上分为2部分,然后再归并这俩有序数组为一个整体有序数组2)自然用master公式计算得知,归并排序的时间复杂度为o(nlog(n))

    10大排序算法之四:归并排序【稳定的】,复杂度中,系统常用归并排序

    提示:整个算法界,一共有十大排序算法,每一个算法都要熟悉,才算是算法入门

    算法界的十大排序算法分别是:
    选择排序、冒泡排序、插入排序、堆排序、希尔排序、归并排序、快速排序、桶排序、计数排序,基数排序
    (1)选择排序:10大排序算法之一:选择排序【不稳定】,一般不用选择排序的
    (2)冒泡排序:10大排序算法之二:冒泡排序【稳定的】,但复杂度高,一般不用冒泡排序的
    (3)插入排序:10大排序算法之三:插入排序【稳定的】,复杂度高,系统常在数据少时用插入排序。

    在这里插入图片描述
    如果你想进互联网大厂,至少这上面的其中最重要的8种,是必须熟练掌握的:
    去掉希尔排序,希尔排序是一种改进的插入排序算法——所以只需要掌握插入排序
    桶排序中最重要的就是计数排序和基数排序,都是桶的思想
    在这里插入图片描述
    根据算法复杂度低一点的,又稳定的
    咱们可以最常用的算法实际上就四种:
    插入排序(o(n^2))【当数据量小时,这个方法简单】【稳定】、
    堆排序o(nlog(n))【不稳定】、
    归并排序o(nlog(n))【稳定】,
    快速排序o(nlog(n))(虽然快排不稳定,但是很多不需要稳定情况下,快排非常快)
    因此,o(n)的桶排序很少用,除非面试官特别申明,否则都用比较排序。
    归并排序是最常用的,复杂度低,而且稳定,达到了一个非常好的折中。


    题目

    请你手撕插入排序的算法代码,要求将arr中的数字升序排序。


    一、审题

    示例:arr = 5 3 1 8 6 2 4
    让其最终变为:arr= 1 2 3 4 5 6 8


    二、归并排序

    归并排序的思想:
    之前咱们学过递归思想的时间复杂度用master公式来求:
    递归思想求arr中最大值,递归函数先调用处理几部分,然后整理和归并信息返回

    运用递归思想,将arr分为L–mid–R两部分,先排序左边,先排序右边再归并左右2部分,最终让L–R上有序
    比如,案例中的arr
    (1)递归分成0–3和4–6两部分
    (2)0–3又分为0–1,2–3两部分,4–6又分为4–5,6–6两部分
    base case:遇到一个元素,直接返回,不操作
    (3)此时0和1位置都是独立有序的,所以归并arr中L–mid,mid+1–R两部分,merge(arr,L,mid,R)使得L–R上整体有序。
    看下图:
    在这里插入图片描述
    (4)归并函数:merge(arr,L,mid,R)咋做呢?
    双指针,p1指向L,p2指向mid+1,比较p1和p2,谁小,先复制谁?用help缓存起来
    当一边复制完了以后,还剩下元素那边直接放到help屁股
    最后将help转移还给arr的L–R中,可见help就是R-L+1这么长的缓存数组

    看一个案例:上面有一次左右递归排序之后,arr=1 3 5 8 2 4 6
    L=0,mid=3,R=6
    因此调用merge(arr,L, mid, R)=merge(arr,0,3,6)
    (1)p1=L=0,p2=mid+1=4,对比[p1]<[p2],先搬1,p1++=1;
    (2)对比[p1]>[p2],先搬2,p2++=5;
    (3)对比[p1]<[p2],先搬3,p1++=2;
    (4)对比[p1]>[p2],先搬4,p2++=6;
    (5)对比[p1]<[p2],先搬5,p1++=3;
    (6)对比[p1]>[p2],先搬6,p2++=7;
    此时,p2已经越界,超过R了
    所以停止
    看左边还没有搬完呢,将左边剩下的所有,8搬到help后边
    然后将help转移给arr的L–R上
    在这里插入图片描述
    手撕代码:
    归并排序,宏观调度室是:左右两部分递归排序,排序好的俩有序数组,用来归并成一个有序数组,放回L–R上

    //归并排序,复习
        //首先,准备merge L--mid--R上归并,这个很重要!!!
        public static void mergeReview(int[] arr, int L, int mid, int R){
            if (L >= R) return;
            //归并是至少俩个以上的元素,help转移
    
            int[] help = new int[R - L + 1];//这么长
            int p1 = L;
            int p2 = mid + 1;
            //先merge,小的在前,大的在后,相对位置不变
            int i = 0;//用来给help索引的
            while (p1 <= mid && p2 <= R){
                help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];//i每次增,谁小先搬谁,然后p++
            }
            //然后二选一,把剩下那个部分全部copy给help
            while (p1 <= mid) help[i++] = arr[p1++];
            while (p2 <= R) help[i++] = arr[p2++];
    
            //最后把help转移给arr
            for (int j = 0; j < help.length; j++) {
                arr[L + j] = help[j];//从L开始放
            }
        }
    
        //有了merge这个函数,我们就可以用递归思想,做归并排序了
        public static void mergeSortReview(int[] arr, int L, int R){
            //2个以上,就可以排序
            //base case
            if (L == R) return;
    
            //先递归排序左右两部分,然后归并排序
            int mid = L + ((R - L) >> 1);
            mergeSortReview(arr, L, mid);
            mergeSortReview(arr, mid + 1, R);
    
            mergeReview(arr, L, mid, R);//归并排序
        }
    

    测试:

    //常用的交换数组函数
        public static void swap(int[] arr, int i, int j){
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    
        //对数器之构建随机数组
        public static int[] createArray(int arrSize, int maxValue){
            int[] arr = new int[arrSize];
            for (int i = 0; i < arrSize; i++) {
                arr[i] = (int)(maxValue * Math.random());//0-N-1的随机数
            }
            return arr;
        }
    
        public static void checker(){
            //生成检验数组
            int[] arr = createArray(10000,10000);
            int[] arr2 = new int[arr.length];//赋值同样一个数组arr
            for (int i = 0; i < arr.length; i++) {
                arr2[i] = arr[i];//copy即可
            }
            int[] arr3 = new int[arr.length];//赋值同样一个数组arr
            for (int i = 0; i < arr.length; i++) {
                arr3[i] = arr[i];//copy即可
            }
    
            //绝对的正确方法——暴力方法,或系统函数,操作arr
            Arrays.sort(arr);
            //优化方法,操作arr2
            mergeSort(arr2, 0, arr2.length-1);//从0-len-1做归并排序
            mergeSortReview(arr3, 0, arr3.length-1);//从0-len-1做归并排序
    
            //然后两个数组对位校验
            boolean isSame = true;
            for (int i = 0; i < arr.length; i++) {
                if(arr[i] != arr2[i]) {
                    isSame = false;
                    break;//只要有一个不等,不必继续判断了
                }
            }
            System.out.println(isSame == false ? "oops,wrong!" : "right!");
            System.out.println();
            isSame = true;
            for (int i = 0; i < arr.length; i++) {
                if(arr[i] != arr3[i]) {
                    isSame = false;
                    break;//只要有一个不等,不必继续判断了
                }
            }
            System.out.println(isSame == false ? "oops,wrong!" : "right!");
        }
    
    //有了递归思想以后,就可以左右划分做递归排序和融合
        //递归终止条件:当L=R时,return;
        //否则,左边做递归排序,右边做递归排序
        //最后,merge融合放进help数组,merge是亮点,两个轴处于L和mid+1处,双双对比,谁小放左边。
        // 最后全部copy返回给arr
    
        public static void main(String[] args) {
            checker();//对数器校验
        }
    

    结果:

    right!
    
    right!
    

    归并排序的归并那一步merge函数,很重要,在今后很多经典大厂的面试题中,都会用的。


    归并排序的时间复杂度

    之前讲过递归思想的时间复杂度计算master公式,必须死记硬背的:
    今天再说一遍:
    如果递归调用a次(归并排序就是典型的a=2次,左右);
    每一次调用规模为N/b,归并排序的b=2
    除了递归的复杂度之外,还有merge的复杂度,既然i++,则就是o(n)的复杂度,即o(n^d)=o(n),故d=1
    所以有这么一个关系:
    在这里插入图片描述
    归并排序中a=2,b=2,d=1
    所以:归并排序的时间复杂度为o(nlog(n))
    在这里插入图片描述
    懂了吧!


    总结

    提示:重要经验:

    1)归并排序的核心思想,先把arr的L–R上分为2部分,然后再归并这俩有序数组为一个整体有序数组
    2)自然用master公式计算得知,归并排序的时间复杂度为o(nlog(n))

    展开全文
  • 稳定排序之归并排序

    2016-04-11 22:04:06
    首先要介绍如何将两个已排序的数组合并,因为这是递归排序的核心思想:首先要介绍如何将两个已排序的数组合并,因为这是递归排序的核心思想:void merge_array(int a[], int first, int mid, int last, int temp[]){...

    今天学习递归,看了教程居然一下子没看懂,发现不好的教程真是毁人,特此记录一下好的教程。
    首先要介绍如何将两个已排序的数组合并,因为这是递归排序的核心思想:首先要介绍如何将两个已排序的数组合并,因为这是递归排序的核心思想:

    void merge_array(int a[], int first, int mid, int last, int temp[]){
        int i=first;
        int j=mid+1;
        int k=0;
        while(i<=mid && j<=last){
            if(a[i]<a[j])
                temp[k++]=a[i++];
            else
                temp[k++]=a[j++];
        }
        while(i<=mid)
            temp[k++]=a[i++];
        while(j<=last)
            temp[k++]=a[j++];
        for(int m=0;m<k;m++){
            a[first+m]=temp[m];
        }
    }

    接下来我们把这个函数应用到归并排序函数中去,其实就是递归使用该核心函数。

    void merge_sort(int a[],int first, int last, int temp[]){
        if(first<last){
            int mid=(first+last)/2;
            merge_sort(a,first,mid,temp);
            merge_sort(a,mid+1,last,temp);
            merge_array(a,first,mid,last,temp);
        }
    }

    我们可以发现合并有序数列的效率是比较高的,即merge_array的时间复杂度是O(n)。在merge_sort中我们将数列不断二分,因此执行merge_array的次数是logN次。所以最终我们归并排序的时间复杂度就是两者相乘,即O(NlogN)

    展开全文
  • 值得注意的是归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。算法描述归并操作的工作原理...
  • 归并排序由冯·诺依曼提出,是一种稳定、通用的排序算法求解策略。 归并示例 归指的是利用递归将原数组每次进行二分,分解为两个子数组。 并指的是将两个有序序列合并成一个有序序列的方法。 如设有数列{13, ...
  • 归并排序--稳定的排序

    千次阅读 2018-11-24 09:19:05
    //归并排序 #include&lt;iostream&gt; using namespace std; void merge(int a[], int left, int mid, int right, int* temp) { int i = left; int j = mid + 1; int t = 0; while (i &lt;= mid &...
  • 稳定排序:归并排序

    2017-04-20 16:02:20
    归并排序:对于给定的一组长度为n的记录,利用分治和递归的思想,将记录分为一个个长度为1的子序列,最后再用递归方法将排好序的子序列合并成为越来越大的有序序列。此方法称为2-路归并排序 归并排序一般会用在...
  • 一、归并排序 1、介绍。 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,... 归并排序稳定排序,需...
  • 归并排序算法.docx

    2020-04-05 20:22:20
    归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;...归并排序是一种稳定的排序方法。
  • 归并排序与堆排序

    2022-01-22 09:51:18
    文章目录归并排序思想代码测试分析堆排序(Heap Sort)堆的定义思想实现测试分析 归并排序 思想 排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样...
  • 归并排序 稳定

    2017-07-27 15:42:00
    速度仅次于快排,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列 转载于:https://www.cnblogs.com/zawjdbb/p/7245219.html
  • 个人理解就是特殊的插入排序,只不过是比插入排序步子迈的大一些,跨好几个元素进行比较,在缩小步子。 具体做法是初始化一个增量,逐步缩小增量,对由增量分组的元素进行插入排序; Shell.class public class Shell...
  • 算法 系列博客、 一、时间复杂度、 二、空间复杂度、 三、排序稳定性、 三、局部有序与整体有序、
  • 二路归并排序的基本思想 设数组a中存放了n个数据元素,初始时把它们看成是n个长度为1的有序子数组,然后从第一个有序子数组开始,把相邻的有序子数组两两合并,得到[n/2]个长度为2的新的有序子数组(当n为奇数时,...
  • 归并排序详解

    2022-04-11 12:38:10
    摘要:归并排序是我们常用的八大排序中的一种,其排序思路...配合递归与有序数组合并算法,归并排序能够高效且稳定的完成排序,归并排序的优点在于其时间复杂度低,稳定性高,但是缺点也是有的,那就是空间复杂度很高。
  • 归并排序

    2020-02-07 15:58:20
    归并排序的基本原理为:将序列平分为两个子序列(如果序列为奇数2*i+1个,则第一个子序列为i+1个,第二个子序列为i个),分别对子序列进行排序,再将已经有序的子序列合并,得到完全有序的序...
  • 快速排序&归并排序

    2022-02-09 11:47:10
    1. 快速排序 1)思路(先宏观排序,再局部排序): 从无序数组中选择一个pivot(中心点),小于pivot的数放到左边,大于pivot的数放到右边,得到两个无序数列。再分别对两个无序数列进行排序,...2. 归并排序 ...
  • Python实现归并排序

    2021-07-20 22:45:08
    归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组,再合并数组。 将数组分解最小之后,然后合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就...
  • 具体代码请看:NDKPractice项目的datastructure 1. 稳定排序和不稳定排序: ...2. 归并排序 每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且
  • 十大经典排序之:归并排序 |桶排序

    千次阅读 多人点赞 2021-11-25 22:05:45
    十大经典排序之:选择排序 |堆排序选择排序选择排序原理算法实现例题堆排序排序原理算法实现例题
  • C语言归并排序详解

    2021-05-25 03:36:34
    C语言归并排序详解发布日期:2015-12-31 11:16来源:标签:编程语言C教程C语言归并排序C语言归并排序算法本章我们主要学习C语言实现排序算法之归并排序,对归并排序的原理及实现过程做了非常详细的解读,下面我们就做...
  • 排序算法-归并排序

    千次阅读 2021-12-30 14:53:40
    排序算法-归并排序 算法思想 归并:将两个或者两个以上的有序表组合成一个新的有序表的过程。假定待排序表中含有n个记录,则可以看成是n个有序的子表,每个子表的长度为1,然后两两归并,得到⌈n/2⌉\lceil n/2 \...
  • 详解归并排序

    2022-01-27 16:22:08
    1.归并排序 归并排序使用了分治和递归的思想,将具有n的元素的无序序列划分为n个每个含有一个元素的序列,再将n个有序序列采用二路归并等合并方法进行合并排序成一个有序的序列。 2.归并实现步骤 2.1.划分划分左...
  • 在理解归并排序之前先要理解算法中一个非常重要的思想方法:分冶模式。算法导论中分冶策略定义:将原问题划分为n个规模较小,与原问题结构相似的子问题;递归解决这些子问题,然后再合并其结果,就得到原问题的解。...
  • 归并排序 算法原理 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 算法分析 排序的思想就是将元素无限拆分,直到无可...
  • 归并排序merge_sort模板

    2020-02-29 20:32:26
    归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;...归并排序是一种稳定的排序方法。
  • 归并与归并排序

    2021-02-01 23:10:17
    归并排序,同样是利用分治思想的典型算法例子,下面简单总结下归并排序。一、归并的概念归并是这样一种概念,它针对两个或者多个有序的数组,是合并这多个有序数组并进行排序的一种手段,它的主要处理方法是每次都找...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 43,526
精华内容 17,410
关键字:

归并排序是否稳定