数据结构与算法

归并排序

归并排序是一种基于分治技术的排序技术。最坏情况时间复杂度为Ο(n log n),是最受推崇的算法之一。
合并排序首先将数组分成相等的两半,然后将它们以排序的方式合并。

归并排序是如何工作的?

为了理解归并排序,我们采用如下的未排序数组-
未排序数组
我们知道归并排序首先将整个数组迭代地分成相等的两半,除非达到原子值。我们在这里看到一个包含 8 个项目的数组被分成两个大小为 4 的数组。
合并排序分区
这不会改变原始项目的出现顺序。现在我们将这两个数组分成两半。
合并排序分区
我们进一步划分这些数组,我们得到了不能再划分的原子值。
合并排序分区
现在,我们以与分解它们完全相同的方式组合它们。请注意这些列表的颜色代码。
我们首先比较每个列表的元素,然后将它们以排序的方式组合到另一个列表中。我们看到 14 和 33 处于排序位置。我们比较 27 和 10,在 2 个值的目标列表中,我们首先放置 10,然后是 27、我们更改了 19 和 35 的顺序,而 42 和 44 是按顺序放置的。
合并排序合并
在合并阶段的下一次迭代中,我们比较两个数据值的列表,并将它们合并成一个找到的数据值列表,将所有数据按排序顺序排列。
合并排序合并
最终合并后,列表应如下所示-
合并排序
现在我们应该学习归并排序的一些编程方面。

算法

合并排序继续将列表分成相等的两半,直到它不能再被分割。根据定义,如果它只是列表中的一个元素,则对其进行排序。然后,归并排序合并较小的排序列表,同时保持新列表的排序。
Step 1if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

伪代码

现在我们将看到归并排序函数的伪代码。正如我们的算法指出的两个主要功能-分割和合并。
合并排序与递归一起工作,我们将以相同的方式查看我们的实现。
procedure mergesort( var a as array )
   if ( n == 1 ) return a
   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]
   l1 = mergesort( l1 )
   l2 = mergesort( l2 )
   return merge( l1, l2 )
end procedure
procedure merge( var a as array, var b as array )
   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
    
end procedure
昵称: 邮箱:
Copyright © 2022 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4