首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

归并排序详解 和逆序数计算

归并排序(MERGE-SORT)是建立在归并操作上一种有效排序算法,该算法是采用分治法(Divide and Conquer)一个非常典型应用。...(摘自baidu) 归并排序核心思想是将两个已经排序序列合并成一个序列,那如何得到两个已经排序序列呢?...我们知道, 如果一个序列只有一个元素,那该序列是已经排序,这样我们就可以利用分治思想,将未排序序列划分成更小序列,只到我们可以很方便对小序列进行排序(比如划分到序列只有一个元素, 或者序列很小可以方便使用其它排序算法进行排序...(csdn) 归并排序效率是比较高,设数列长为N,将数列分开成小数列一共要logN步,每步都是一个合并有序数过程,时间复杂度可以记为O(N),故一共为O(N*logN)。...因为归并排序每次都是在相邻数据中进行操作,所以归并排序在O(N*logN)几种排序方法(快速排序归并排序,希尔排序,堆排序)也是效率比较高

1.2K50

使用归并排序计算序数

计算序数 在很早之前,我曾经发过一篇文章,讲的是冒泡排序交换次数就是逆序数。可是,这样计算序数的话,时间成本就很高,比较冒泡是时间复杂度为O(N²)算法呢!那怎么办呢?...其实,我们可以使用归并排序思想来计算序数。...(以下内容需要先了解归并排序,具体讲解可以看我这一篇文章:) 数据结构之归并排序 我们会发现,在进行升序归并排序时,每一次后方元素移到前面来移动距离就是本次操作序数。...那么我们思考之后可以得出,每一步操作序数就是n1-i 具体得看下面这个图: 由于每一层递归结束之后,左右两边都变成了已经升序排序数组,那么自然地,当右边元素小于左边元素时候,把它移到前面的逆序数就是...经过上面的分析,我们可以知道,我们只需要在归并排序合并函数里面,负责处理L[js1]>R[js2]那部分代码里面做一些修改,就可以实现计算序数目的。

28320
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    ☆打卡算法☆LeetCode 33、搜索旋转排序数算法解析

    一、题目 1、算法题目 “给定一个旋转后数组和整数target,如果数组中存在整数target,则返回它下标。” 题目链接: 来源:力扣(LeetCode) 链接:33....搜索旋转排序数组 - 力扣(LeetCode) (leetcode-cn.com) 2、题目描述 整数数组 nums 按升序排列,数组中值 互不相同 。...给你 旋转后 数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它下标,否则返回 -1 。...4,5,6,7,0,1,2], target = 0 输出: 4 示例 2: 输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1 二、解题 1、思路分析 这个题可以使用二分查找方法去查找指定元素...首先,在这道题中数组本身不是有序,翻转后只有部分是有序,比如按照整数6来说,从6分成前后两部分,总有一部分是有序,所以我们二分查找时候也需要确定哪个区域是有序,之后再用二分查找。

    17820

    归并排序算法过程图解

    它是建立在归并操作上一种有效排序算法,该算法是采用分治法(Divide and Conquer)一个非常典型应用。...第五步,将序列b中所有剩余元素直接放入r中即可,不用做任何比较了,直至b变空,二路归并结束。 ? 归并算法 归并排序算法我们通常用递归实现。...归并排序例子 我们仍然用冒泡排序和其改进后快速排序算法,直接选择排序和堆排序算法,直接插入排序到希尔排序改进这三篇中用到排序列 3 2 5 9 2 归并排序伪代码...start<end)都返回了,然后执行到merge,执行完merge后,sort[0,1]出栈,此时栈顶为sort[0,2]函数,可以看出它前半部分已经计算完,只需要计算后半部分,即第二个sort,...归并排序空间复杂度为O(n),会占用内存。 总之,归并排序虽然比较占用内存,但却是一种效率高且稳定算法

    1.5K110

    八十二、归并排序求取复杂序数

    「@Author:Runsen」 逆序数,我在很多面试题都见过,本质上来说难度是比较大,因为如果使用暴力法当数据量一大,必然就会爆掉。你现在就要记住逆序数就是考归并排序。...设计一个算法求一个数组序数 比如给出数组nums = [11, 8, 3, 9, 7, 1, 2, 5],我可以求出[(11, 8), (8, 3), (11, 3), (11, 9), (7, 1...归并排序过程: 将数组拆分成左右两个部分 对左边进行归并排序 对右边进行归并排序 合并左右两边 我们可以发现一点, 完成第三步操作之后,并不会改变这样逆序对(一个数在左边,另一个数在右边)个数....利用归并排序计算序数方法太巧妙了,但是只要提醒你一下使用分治思想,或者使用归并排序思想解决这道问题你可能就有思路了。...归并排序实际上会把数组分成两个有序部分,我们不妨称其为左和右,归并排序过程中会将左右两部分合并成一个有序部分,对于每一个左右部分,我们分别计算其逆序数,然后全部加起来就是我们要求序数,详细思路在代码中注释了

    37220

    算法归并排序算法编码和优化

    参考资料 《算法(第4版)》          — — Robert Sedgewick, Kevin Wayne 归并排序概念 归并排序实现我是这样来描述:先对少数几个元素通过两两合并方式进行排序...(也叫自顶向下归并排序和自底向上归并排序) 这两种归并算法虽然实现方式不同,但还是有共同之处: 1....无论是基于递归还是循环归并排序, 它们调用核心方法都是相同:完成一趟合并算法,即两个已经有序数组序列合并成一个更大序数组序列  (前提是两个原序列都是有序!) 2....从排序轨迹上看,合并序列长度都是从小(一个元素)到大(整个数组)增长 单趟归并算法 单趟排序实现分析 下面我先介绍两种不同归并算法调用公共方法, 即完成单趟归并算法。...(两个已经有序数组序列合并成一个更大序数组序列) 在开始排序前创建有一个和原数组a长度相同辅助数组aux 单趟归并过程如下: 1.

    1.3K80

    ☆打卡算法☆LeetCode 81、搜索旋转排序数组 II 算法解析

    一、题目 1、算法题目 “给定一个整数数组,整数数组会在某一个位置进行旋转,然后给定一个整数,判断整数是否在数组中。” 题目链接: 来源:力扣(LeetCode) 链接:81....搜索旋转排序数组 II - 力扣(LeetCode) (leetcode-cn.com) 2、题目描述 已知存在一个按非降序排列整数数组 nums ,数组中值不必互不相同。...给你 旋转后 数组 nums 和一个整数 target ,请你编写一个函数来判断给定目标值是否存在于数组中。...,是否存在给定值,这道题跟33题搜索旋转排序数类型很相似,是在33题基础上修改而来,33题使用了二分查找方法。...那么对于这道题也可以使用二分查找方法,这个首先需要确定左右取件是否是有序

    20240

    谁才是最强排序算法: 快速排序, 归并排序, 堆排序

    )~O(n) 不稳定 可以看到,到达nlogn级别的排序算法,一共有三种,分别是堆排序归并排序以及快速排序,其中只有归并排序最稳定。...那么,为什么要说快速排序平均情况是最快呢? 实际上在算法分析中,大O作用是给出一个规模下界,而不是增长数量下界。...因此,算法复杂度一样只是说明随着数据量增加,算法时间代价增长趋势相同,并不是执行时间就一样,这里面有很多常量参数差别,比如在公式里各个排序算法前面都省略了一个c,这个c对于堆排序来说是100,...另外, 堆排比较几乎都不是相邻元素,对cache极不友好, 数据读取开销变大。在计算机进行运算时候,数据不一定会从内存读取出来,而是从一种叫cache存储单位读取。...下面是一个测试数据: 测试平均排序时间:数据是随机整数,时间单位是s 数据规模 快速排序 归并排序 希尔排序排序 1000万 0.75 1.22 1.77

    1K30

    算法-数组归并排序计算逆序对个数PHP实现

    在数组中两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中逆序对总数P。并将P对1000000007取模结果输出。...即输出P%1000000007 1.数组归并排序 2.归并排序比较左右两个堆数组中元素大小时,进行计数,倒着比较,因为左堆倒第一如果比右堆倒第一大,那么就比右堆所有都大 mergeSort...mergeSort($data,0,count($data)-1,$temp,$num); $num%=1000000007; return $num; } //1.利用分治法思想,递归切分排序元素...function mergeSort(&$A,$left,$right,$temp,&$num){ //2.最左只能小于最右,等于时候就一个元素,大于是不可能 if...//5.递归右半区 mergeSort($A,$mid+1,$right,$temp,$num); //6.合并两个有序数组为一个有序数

    70920

    归并排序算法编码和优化

    (也叫自顶向下归并排序和自底向上归并排序) 这两种归并算法虽然实现方式不同,但还是有共同之处: 无论是基于递归还是循环归并排序, 它们调用核心方法都是相同:完成一趟合并算法,即两个已经有序数组序列合并成一个更大序数组序列...从排序轨迹上看,合并序列长度都是从小(一个元素)到大(整个数组)增长。 单趟归并算法 单趟排序实现分析 下面我先介绍两种不同归并算法调用公共方法, 即完成单趟归并算法。...(两个已经有序数组序列合并成一个更大序数组序列) 在开始排序前创建有一个和原数组a长度相同辅助数组aux 单趟归并过程如下: 首先将原数组中排序序列拷贝进辅助数组相同位置中,即将a[...递归归并排序优化 优化点一:对小规模子数组使用插入排序 用不同方法处理小规模问题能改进大多数递归算法性能,因为递归会使小规模问题中方法调用太过频繁,所以改进对它们处理方法就能改进整个算法。...实际上,我们可以通过一种看起来比较方式把这个拷贝过程给去除掉。。。。。

    1.2K60

    一道归并排序解析

    ://blog.csdn.net/sinat_35512245/article/details/53710263 设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按二路归并方法对该序列进行一趟扫描后结果为...---- 二路归并:如果序列中有n 个记录,可以先把它看成n个子序列,每个子序列中只包含一个记录,因而都是排好序。...二路归并排序先将每相邻两个子序列合并,得到n/2(向上取整)个较大有序子序列,每个子序列包含2个记录。再将这些子序列两两合并。如此反复,直到最后合并成一个有序序列,排序即告完成。...设有数列{6,202,100,301,38,8,1} 初始状态:6,202,100,301,38,8,1 第一次归并后:{6,202},{100,301},{8,38},{1}; 第二次归并后:{6,100,202,301...,M,C,W 第一次归并后:{D,Q},{F,X},{A,P},{B,N},{M,Y},{C,W}; 第二次归并后:{D,F,Q,X},{A,B,N,P},{C,M,Y,W}; 第三次归并后:{A,B,

    29220

    排序算法在JDK中应用(一)归并排序

    ()和Arrays.parallelSort(),前者是传统排序算法,后者是JDK8新增并行排序算法,基于fork/join框架,今天主要是分析Arrays.sort()底层实现。...compareTo()方法进行比较排序,并且使用归并排序。...,总结而言就是当待排序数组长度大于等于286时开始考虑使用归并排序。...在此同时还需要考虑条件是待排序数组是否是基本有序,JDK采用办法是将待排序数组分成若干个单调递增或者递减数组,如果分成小数组个数 大于67就认为这个数组基本上是无序此时就直接调用了快速排序...参考文献 双轴快排原理解析 JDK源码解析(1) END 主 编 | 张祯悦 责 编 | 杨 旭 where2go 团队 ---- 微信号:算法与编程之美

    88030

    Python 算法高级篇:归并排序优化与外部排序

    引言 在计算机科学中,排序是一项基本任务,而归并排序( Merge Sort )是一种著名排序算法,它具有稳定性和良好时间复杂度。...下面是一个简单归并排序算法 Python 实现: def merge_sort(arr): if len(arr) > 1: mid = len(arr) // 2 # 找到数组中间位置...O ( n log n ),它是一种稳定排序算法,但它需要额外空间来存储临时数组。...通过这种方式,你可以比较它们性能并选择最适合你应用版本。 5. 结论 归并排序是一种经典排序算法,它使用分治策略和合并操作,具有稳定性质和较低时间复杂度。...通过进行优化,例如自底向上归并排序和减少内存使用外部排序,我们可以提高归并排序性能和适用性。根据应用需求和资源限制,选择合适排序算法版本,以获得最佳性能。

    35241

    ☆打卡算法☆LeetCode 153. 寻找旋转排序数组中最小值 算法解析

    一、题目 1、算法题目 “给定一个数组,按照升序排列,经过1-n次旋转后,得到输入数组,找出数组中最小元素。” 题目链接: 来源:力扣(LeetCode) 链接: 153....寻找旋转排序数组中最小值 - 力扣(LeetCode) 2、题目描述 已知一个长度为 n 数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。...你必须设计一个时间复杂度为 O(log n) 算法解决此问题。...二、解题 1、思路分析 这道题是要找出升序排序数组经过翻转后最小元素。 一看这道题,嚯,这么简单,直接一波循环找到,管你翻转不翻转呢,结果要求时间复杂度O(log n),那就不能循环遍历了。...也就是找到一个中位数,中位数一边是有序,将有序数最小值与当前保存最小值比较,继续二分遍历找中位数,直到左指针大于右指针。

    20020

    讨厌算法程序员 6 - 归并排序

    分而治之 分而治之 从算法设计分类上来说,插入排序属于增量方法。在排序好子数组A[1 ‥ j-1]后,再将单个元素A[j]插入子数组适当位置,产生排序子数组A[1 ‥ j]。...整个算法就是不断以此方法增量插入,直到子数组包含了所有数组元素。 本篇将要介绍归并排序,是用另一种思想来解决排序问题,在算法设计分类上属于分治法。...归并排序伪码 归并排序按照分治法三个步骤如下: 分解:分解待排序n个元素序列,变成各具n/2个元素两个子序列; 解决:递归调用自身排序两个子序列; 合并:合并两个已排序子序列以产生最终排序序列...上一篇合并算法中已经解决了合并算法MERGE,归并排序就剩下如何进行分解,和递归调用了。...一个例子 一个有8个元素数组A[5, 2, 4, 7, 1, 3, 2, 6],采用归并排序图示如下图。图中下方蓝区部分是上面白区数组不同时刻镜像。

    63340

    快速排序 Vs. 归并排序 Vs. 堆排序——谁才是最强排序算法

    知乎上有一个问题是这样: 堆排序是渐进最优比较排序算法,达到了O(nlgn)这一下界,而快排有一定可能性会产生最坏划分,时间复杂度可能为O(n^2),那为什么快排在实际使用中通常优于堆排序?...)~O(n) 不稳定 可以看到,到达nlogn级别的排序算法,一共有三种,分别是堆排序归并排序以及快速排序,其中只有归并排序最稳定。...那么,为什么要说快速排序平均情况是最快呢? 实际上在算法分析中,大O作用是给出一个规模下界,而不是增长数量下界。...因此,算法复杂度一样只是说明随着数据量增加,算法时间代价增长趋势相同,并不是执行时间就一样,这里面有很多常量参数差别,比如在公式里各个排序算法前面都省略了一个c,这个c对于堆排序来说是100,...下面是一个测试数据: 测试平均排序时间:数据是随机整数,时间单位是s 数据规模 快速排序 归并排序 希尔排序排序 1000万 0.75

    1.4K20

    【数据结构与算法归并排序原理及算法实现

    归并排序 归并排序是采用分治法一个非常典型应用。...归并排序思想就是先递归分解数组,再合并数组 将数组分解到最小之后,合并两个有序数组,基本思路就是比较两个数组最前面的数字,谁小就先取谁,取了后相应指针就往后移动一位。...然后再比较,知道一个数组为空,最后把一个数组剩余部分复制过来即可 文章目录 归并排序 基本实现 这个就是归并算法思想:把一组元素一直拆分到只有一个子元素,之后开始合并,通过Left与Right...依旧是左边游标Left,右边右边Right对比。得到了一个有序数列 ? 这个就是归并算法思想:把一组元素一直拆分到只有一个子元素,之后开始合并,通过Left与Right进行排序。...归并算法代码实现 ''' Create by YO @Time: 2020/4/22 ''' #相除时候两个斜杠无小数部分。

    67830
    领券