【排序】归并类排序—归并排序(逆序数问题)

  • 日期:03-06
  • 点击:(1968)


在排序中,我们可能更熟悉气泡排序和快速排序。合并和排序可能不太熟悉。然而,实际上合并排序也是一个稳定的排序,时间复杂度为O(nlogn)。

merge sort基于分治合并,具有双向合并和多路合并。这里我们只讨论双向合并,基本上每天都使用双向合并。合并排序的实现是求和。应该注意它们之间的区别(在意识形态上没有大的区别,只有在划分和比较中才会有区别)。

合并排序的一个重要应用是找出序列中逆序的数量。当然,逆序数也可以通过树形数组来完成,这里不介绍。

merge sort)

merge和fast rank基于分治算法。分治算法实际上应用得相当多,许多分治算法都使用递归,许多递归算法都是分治算法,但实际上分治和递归是两回事。分而治之就是分而治之。因为面对排序,如果不采取合理的策略。每增加一个数字都会对整体产生很大影响。分而治之就是把整个问题分成类似的子问题。子问题的解决远比整个问题的解决更有效,并且子问题的合并不会占用太多的资源。

合并的想法是这样的:

第一次,整个字符串被一个接一个地分割。第一次,一个接一个()被合并成几对并分成几个2部分。在合并()之后,这样一个部分有序的序列就完成了。

第二次是把两个合并成四个()每个小部分都是有序的。

所以直到最后,只有一个字符串,但是它的总次数是logn。每次手术的时间都很复杂。总的时间复杂度是。

你可能知道分而治之的过程,但这两个过程实际上非常重要。首先,我们得到的两个序列是有序的。事实上,这个想法也很简单,假设两个字符串组合成一个和。我们需要使用额外的数组来按顺序存储这两个字符串。但是,过程如下:

非递归合并

普通合并代码是通过递归实现的。但是也有不使用递归的。如果大多数教科书或考试允许你列出合并的序列,那么缺省值是非递归的,例如,序列的划分是相同的。

递归合并

代码实现中的大多数合并可能是递归合并。递归和分治真的很容易理解。递归可以将问题分解成子问题,这正是划分所需的方法。但是递归地,一劳永逸地,一切都是对的。

递归的概念绝对不同于上面的非递归。你可以考虑非递归:我想考虑当前的合并,如何表达每个开始的头部坐标,是否跨越边界,等等。哈,写起来有点麻烦。

与其说递归,不如说它的过程就是过程,而递归就是过程。

递归实现合并的思想:

也是这样一系列的序列,它的递归实现序列如下(可能会有一些问题,但理解起来还是有帮助的):

所以实现合并排序的代码是:

逆序数字

首先需要知道什么是逆序数字:

数组中的两个数字,如果前面的数字大于后面的数字,那么这两个数字就形成了一个逆序对

,也就是说,例如。看3,后面有2 1,看2,后面有1

例如,逆序数字是。

在数组中,暴力真的可以找到逆序数,但是暴力的方法太复杂,不可取!有什么好方法可以解决这个问题?当前序列我可能不知道有多少个序列。但是我们不知道,如果这个序列是有序的,那么逆序的数量将是0。

观看一个序列后,整个序列中的逆序数量将减少3。因为如果数字123和123的相对位置没有变化。所以我们可以用某种方法来确定逆序的数量。

我们想知道是否有一个过程,如果反向订单的数量发生变化,我们可以记录下来。例如,如果你移动,你可以知道是否有任何变化。这种运动不能盲目,最好是局部有序地进行。合并排序是一个非常合适的结构。因为选择小于0(N2)的复杂度算法是确定的,

看看每一个合并的过程,例如,两个有序序列:假设序列和序列的相邻区域被合并。

并查看整个合并排序。改变过程只需要注意一些相对的变化,即每个合并过程的逆序数被改变和累加,然后得到整个序列的逆序数,直到最后排序的序列!

至于规则,你可以发现在每一个合并过程中,当且仅当右边的数字被提前放在左边,而尚未放在左边的数字是元素减少的逆序数!这需要消化,在代码实现中,需要这样做!

结论

合并排序和逆序编号到此为止!我觉得我已经尽力解释了。如果有任何错误或不好的地方,请改正。如果你能感觉到,请赞美它,并注意波浪。

欢迎关注大众数字:长期输出!