数据结构 - 合并排序算法

合并排序是一种基于分而治之技术的排序技术.最坏情况时间复杂度为Ο(n log n),它是最受尊敬的算法之一.

合并排序首先将数组分成相等的一半,然后将它们组合在一起排序方式.

合并排序如何工作?

为了理解合并排序,我们采用未排序的数组作为以下 :

未排序的数组

我们知道合并排序首先将整个数组迭代地分成相等的一半,除非达到原子价值.我们在这里看到8个项目的数组被分成两个大小为4的数组.

Merge Sort Division

这不会改变原始项目的外观顺序.现在我们将这两个数组分成两半.

Merge Sort Division

我们进一步划分这些数组,我们实现原则值,不能再划分.

Merge Sort Division

现在,我们以完全相同的方式将它们组合起来.请注意这些列表的颜色代码.

我们首先比较每个列表的元素,然后以排序的方式将它们组合到另一个列表中.我们看到14和33处于排序位置.我们比较了27和10,并且在2个值的目标列表中我们首先放置10个,然后是27.我们改变了19和35的顺序,而42和44顺序放置.

Merge Sort Combine

在组合阶段的下一次迭代中,我们比较两个数据值的列表,并将它们合并到找到的数据值列表,将所有数据放在排序的顺序中.

合并排序组合

在最终合并之后,列表应该如下所示;

Merge Sort

现在我们应该学习合并排序的一些编程方面.

算法

合并排序继续将列表分成相等的一半,直到它不再分裂.根据定义,如果列表中只有一个元素,则对其进行排序.然后,合并排序组合了较小的排序列表,同时保持新列表的排序.

 步骤1  : 如果列表中只有一个元素已经排序,则返回. 第2步 : 将列表递归地分成两半,直到它不再被分割. 第3步 : 按排序顺序将较小的列表合并到新列表中.

Pseudocode

现在我们将看到合并排序函数的伪代码.我们的算法指出了两个主要功能 - 分频和分频功能.合并.

合并排序适用于递归,我们将以相同的方式看到我们的实现.

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

要了解C编程语言中的合并排序实现.