精华内容
下载资源
问答
  • 归并排序空间复杂度
    2022-08-31 22:17:49

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

    归并操作编辑
    归并操作,也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。
    如 设有数列{6,202,100,301,38,8,1}
    初始状态:6,202,100,301,38,8,1
    第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;
    第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;
    第三次归并后:{1,6,8,38,100,202,301},比较次数:4;
    总的比较次数为:3+4+4=11;
    逆序数为14;

    稳定性分析编辑
    如果待排序的序列中存在两个或两个以上具有相同关键词的数据,排序后这些数据的相对次序保持不变,即它们的位置保持不变,通俗地讲,就是两个相同的数的相对顺序不会发生改变,则该算法是稳定的;如果排序后,数据的相对次序发生了变化,则该算法是不稳定的。关键词相同的数据元素将保持原有位置不变,所以该算法是稳定的

    更多相关内容
  • 归并排序空间复杂度

    千次阅读 2021-05-29 09:32:03
    归并排序的时间复杂度任何情况下都是 O(nlogn),看起来非常优秀。...那我现在问你,归并排序空间复杂度到底是多少呢?是 O(n),还是 O(nlogn),应该如何分析呢? 如果我们继续按照分析递归时间复

    归并排序的时间复杂度任何情况下都是 O(nlogn),看起来非常优秀。(待会儿你会发现,即便是快速排序,最坏情况下,时间复杂度也是 O(n^2)。)但是,归并排序并没有像快排那样,应用广泛,这是为什么呢?因为它有一个致命的“弱点”,那就是归并排序不是原地排序算法

    这是因为归并排序的合并函数,在合并两个有序数组为一个有序数组时,需要借助额外的存储空间。这一点你应该很容易理解。那我现在问你,归并排序的空间复杂度到底是多少呢?是 O(n),还是 O(nlogn),应该如何分析呢?

    如果我们继续按照分析递归时间复杂度的方法,通过递推公式来求解,那整个归并过程需要的空间复杂度就是 O(nlogn)。不过,类似分析时间复杂度那样来分析空间复杂度,这个思路对吗?

    实际上,递归代码的空间复杂度并不能像时间复杂度那样累加。刚刚我们忘记了最重要的一点,那就是,尽管每次合并操作都需要申请额外的内存空间,但在合并完成之后,临时开辟的内存空间就被释放掉了。在任意时刻,CPU 只会有一个函数在执行,也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小,所以空间复杂度是 O(n)

    思考

    • 如果数组元素个数n,归并排序过程需要多少个临时数组呢?
    2+4+8+....+n/2=?
    
    • 归并排序的空间复杂度为何不能累加?
    • 归并排序为何需要临时数组?
    合并的时候暂存元素,为何不能原位排序,因为需要的临时数组不止一个
    
    • 归并排序的排序是在拆分还是在合并时进行的?

    总结

    • 归并排序的空间复杂度是O(n)
    • 归并排序应用不如快排广泛,因为需要更多的内存空间
    • 递归代码的空间复杂度并不能像时间复杂度那样累加
    • 归并排序的排序是在每一次合并时进行的,也就是说每个临时数组最终都是有序的

    参考

    归并排序的时间复杂度_鸭梨的博客-CSDN博客

    归并排序图解_鸭梨的博客-CSDN博客

    展开全文
  • 归并排序空间复杂度O(1)的实现

    千次阅读 2016-06-27 22:29:39
    正常的归并排序是利用分治法,即分解,解决,合并/* tmp_array[]:辅助数组。 left_pos:数组左半部分的游标 left_end:左边数组的右界限 */ void Merge(int array[], int tmp_array[], int left_pos, int right_pos...

    正常的归并排序是利用分治法,即分解,解决,合并

    //O(n)Membery mergeSort
        public void mergeSort(int[] nums)
        {
            int n = nums.length;
            helper(nums,  0, n-1);
        }
        private void helper(int[] nums1,int b, int e)
        {
            if(b < e) 
            {
                int mid = (b + e) >> 1;
                helper(nums1,  b, mid);
                helper(nums1,  mid+1, e);
                merge(nums1, b,mid,e);
            }
        }
        void merge(int[] nums1,int b, int m,int e)
        {
            int[] nums2 = new int[nums1.length];
            int i = b, j = m + 1, k = b;
            while(i <= m && j <=e)
            {
                if(nums1[i] <= nums1[j]){nums2[k++] = nums1[i++];}
                else nums2[k++] = nums1[j++];
            }
            while(i <= m){nums2[k++] = nums1[i++];}
            while(j <= e){nums2[k++] = nums1[j++];}
            for(int ii = b; ii <=e; ii++)
            {
                nums1[ii] = nums2[ii];
            }
        }

    显然利用临时数组,空间复杂度为O(N)
    倘若在merge操作时,可以只使用O(1)的空间。
    答案是可以的!!
    首先让我们熟悉一下旋转的操作。
    旋转:
    比如: abcdefg 以d为轴心旋转,得到efgabcd,可以通过如下算法实现。
    步骤1:对abcd和efg进行reverse ,得到dcba gfe
    步骤2:对整体进行reverse,即得到结果 efg abcd

    在merge时:
    比如:2468 3578 L1:2468 L2:3578,要将L1和L2合并
    步骤:
    1、确定3在整体中的位置,即在2和4之间。
    2、对 468 3进行上述旋转操作

        1、各自reverse 864 3
        2、整体reverse 3 468
    

    3、repeat 直至数组越界。
    T(n) = 2T(n/2)+O(2n)
    O(nlg2n)

    展开全文
  • 归并排序、时间复杂度、空间复杂度、稳定性分析

    目录

    1.题目

    2.思路

    归并排序——nlogn

    思想——递归

    代码

    时间复杂度——O(nlogn)

    空间复杂度——O(n)

    稳定性——稳定

    3.结果

    1.题目

    2.思路

    这个题可以作为练习手写各种排序的场景题。这里回顾一下归并排序。

    归并排序——nlogn

    思想——递归

    每次都把这个数组分成两堆【0, mid】和 【mid + 1, end】,分别对两堆进行排序,然后再合并两个有序的数组,中间借助了一个temp[]数组。这里借助的是递归的思想,每次都把数组分成两堆。比如在排序前半部分的时候,也就是【0, mid】的时候,同样的也是把这个数组分成两堆,然后分别排序好之后,然后再合并。所以会不断地递归下去。直到不能分成两堆为止。

    代码

    • 归并排序主函数为public void mergeSort(int[]nums, int start, int end)
    • 合并两个有序数组的函数public void merge(int[]nums, int start, int mid, int end)
    • 注意归并排序结束条件:if(start >= end) return ;
    • 注意借助了一个暂时的数组存放合并好的数组temp[]
    class Solution {
        public int[] sortArray(int[] nums) {
            int n = nums.length;
            mergeSort(nums, 0, n - 1);
            return nums;
        }
        // 归并排序
        public void mergeSort(int[]nums, int start, int end){
            if(start >= end) return;
    
            int mid = start + (end - start) / 2;
            mergeSort(nums, start, mid);
            mergeSort(nums, mid + 1, end);
    
            // 合并到一起
            merge(nums, start, mid, end);
            return ;
        }
    
        // 合并两个有序的数组到一起
        public void merge(int[]nums, int start, int mid, int end){
            int[]temp = new int[end - start + 1];
            int i = start, j = mid + 1, k = 0;
            while(i <= mid && j <= end){
                if(nums[i] <= nums[j]){  //如果这里<= ,那么就是稳定的,如果是<,那么就是非稳定的
                    temp[k++] = nums[i++];
                }
                else{
                    temp[k++] = nums[j++];
                }
            }
    
            // 跳出循环有两个可能
            while(i <= mid){
                temp[k++] = nums[i++];
            }
    
            while(j <= end){
                temp[k++] = nums[j++];
            }
    
            // 更新nums
            for(int l = start; l < start + temp.length; l++){
                nums[l] = temp[l - start];
            }
            return ;
        }
    }

    时间复杂度——O(nlogn)

    我们可以把时间分成两块乘积,一个是把一个数组分成两堆的时间。一个是合并两个有序数组的时间。分别来简单计算一下,首先是第一次会把数组分成两堆,下一次总共就会有4堆,一直往下,相当于是一颗满二叉树,这个满二叉树的深度为logn,也就是需要nlogn时间.

    对于另外一块,合并两个有序数组的时间,因为会遍历这两个数组的元素各一次,所以是O(n), 不管分成多少堆,每一次的合并数组的时间都是O(n),因为数组总元素没有变化。

    所以最终就是nlogn的时间复杂度。

    空间复杂度——O(n)

    因为借助了临时数组来保存结果。所以是O(n)

    稳定性——稳定

    稳定性:就是如果两个值相同,排序完后,这两个元素的相对位置没变化,那么就说明是稳定的。

    这里归并的稳定性主要取决于合并两个有序数组的函数merge()的写法。

    比如我这里写得是<=,那么就是稳定的。因为假如nums[i] == nums[j],那么我们是先把nums[i]放在temp数组的前面的,所以相对顺序并不会改变。所以是稳定的。

    我们在讨论归并排序的时候,因为他可以是稳定的,所以这个方法一般被称为稳定的排序算法。

    3.结果

    展开全文
  • 归并排序时间、空间复杂度

    千次阅读 2021-05-31 09:46:07
    算法 时间avg 时间min 时间max 空间avg 稳定性 归并 O(nlog(n)) O(n) O(nlog(n)) n 稳定
  • 归并排序及其复杂度分析

    千次阅读 2018-04-19 20:42:27
    /* * (二分)归并排序(稳定算法) * 基本思想:将数组递归分成越来越小的数集,直到每个数集只有一个数 ...* 空间复杂度分析:归并排序需要一个临时temp[]来储存归并的结果,所以 O(n) * * 基本...
  • 通过图解分析归并排序流程,以及使用Master公式计算时间复杂度
  • 注:转载:图解排序算法(四)之归并排序 - dreamcatcher-cx - 博客园 作者:dreamcatcher-cx出处:<http://www.cnblogs.com/chengxiao/> 本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段...
  • 在排序算法中快速排序的效率是非常高的,但是还有种排序算法的效率可以与之媲美,那就是归并排序归并排序和快速排序有那么点异曲同工之妙,快速排序:是先把数组粗略的排序成两个子数组,然后递归再粗略分两个子...
  • 两个有序序列L1和L2,利用归并排序的merge,将数组A排序。要求:空间复杂度为O(1) 思路:利用原数组A的空间,两个下标i和j分别遍历L1和L2。注意:当L2当前元素较小时,会覆盖L1的元素。可以利用插入排序,将arr[j]...
  • 排序算法及实现
  • 归并排序 将要排序的元素划分为单个的元素(分),然后一步步将分开的元素合并起来,同时进行排序。(归)。如下图所示: 分到最后,每个元素都是单独的一组,第一次拆分的数列是[52,45,77,33]和[4,5,22,77,43],...
  • 归并排序归并排序时间复杂度、例题
  • 三种排序算法时间复杂度均为nlgn,空间复杂度不同 快速排序 不需要额外内存 消耗lgn到n的栈空间 public class QuickSort { static void quickSort(int[] array){ quickSortofRange(array, 0, array.length-1); ...
  • 归并排序时间复杂度分析

    万次阅读 多人点赞 2017-09-09 10:18:34
    归并排序时间复杂度分析主要参考了他的博文,他还讲解了其他排序的时间复杂度分析及算法实现。可以说合并排序是比较复杂的排序,特别是对于不了解分治法基本思想的同学来说可能难以理解。总时间=分解时间+解决问题...
  • 序言:第一次听到这个算法感觉这个名字很有意思,甚至感觉到很高大上,仔细一看其实以前也看到过,就是字符串的三重反转算法,只是不知道它的这个高大上...但是如果加上限制空间复杂度只能是O(1),又该如何解决呢?...
  • 点击上方“五分钟学算法”,选择“星标”公众号重磅干货,第一时间送达转自景禹今天分享一道很经典的题目,如何将归并排序空间复杂度降低到 ,希望你看完有所收获~~题目解析 对于一个整数数组...
  • 归并排序和快排的空间复杂度对比

    千次阅读 2019-04-15 10:17:33
    归并排序和快排都用到了递归调用,但是因为递归函数所处的位置不一样,所以,导致需要的空间复杂度不一样。 其实递归调用占用的空间就是因为一个函数还没有进行完,那么去执行下一个递归的函数,那么上一个还没有...
  • 【算法】快速排序与归并排序对比

    千次阅读 2021-07-27 21:51:09
    算法 系列博客、 一、时间复杂度、 二、空间复杂度、 三、排序稳定性、 三、局部有序与整体有序、
  • 归并排序,其实就是递归+合并。
  • 空间复杂度 稳定性 复杂性 插入排序 O(n2) O(n2) O(n) O(1) 稳定 简单 冒泡排序 O(n2) O(n2) O(n) O(1) 不稳定 较复杂 归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定 较复杂 快速排序 O(nlog2n) O(n2...
  • 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段...
  • 最容易想到的实现方式是自顶向下的递归实现,考虑到递归调用的栈空间,自顶向下归并排序空间复杂度是O(logn)。如果要达到 O(1)的空间复杂度,则需要使用自底向上的实现方式。 解答一:归并排序(递归法,空间...
  • 如果没有要求空间复杂度为O(1),可以遍历链表并将每个节点的值存入vector中,利用sort( )对vector排序后,最后再遍历一次链表,将排序... 归并排序O(nlogn);2. 快慢指针定位链表中间节点。 复杂度分析: T(n) ...
  • 算法:归并排序及优化

    千次阅读 2022-04-25 17:41:54
    O(nlogn) 最好时间复杂度:O(nlogn) 平均时间复杂度:O(nlogn) 空间复杂度:O(n) 稳定性:稳定 算法分析 归并排序比较占用内存,但速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的...
  • 引言: 算法是计算机科学中的基础,程序=算法+数据结构,算法描述了我们将如何来处理数据的过程。本文将介绍两种算法的实现以及其中一种算法的复杂度分析过程。
  • 冒泡排序的平均时间复杂度为 O(n²) ,最坏时间复杂度为 O(n²) ,最好的时间复杂度是O(n),空间复杂度为 O(1) ,是稳定排序。 function swap(arr, index1, index2) { var temp = arr[index1]; arr[index1] = arr...
  • 浅谈归并排序

    2021-01-12 19:59:58
    为此接下来将会介绍两种时间复杂度为O(nlogn)的排序算法,归并排序和快速排序。这两种排序比较常见于大规模的数据排序中。今天这篇文章我们先来讲解归并排序。 一、归并排序的原理 归并排序的原理很好理解,它运用了...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 49,585
精华内容 19,834
关键字:

归并排序空间复杂度