合并排序(Merge Sort)
优质
小牛编辑
135浏览
2023-12-01
合并排序是一种基于分而治之技术的排序技术。 在最坏情况下的时间复杂度为0(n log n)时,它是最受尊敬的算法之一。
合并排序首先将数组分成相等的一半,然后以排序的方式组合它们。
合并排序如何工作?
要理解合并排序,我们采用未排序的数组,如下所示 -
我们知道,除非实现原子值,否则合并排序首先将整个数组迭代地分成相等的一半。 我们在这里看到,8个项目的数组被分成两个大小为4的数组。
这不会改变原始项目的外观顺序。 现在我们将这两个数组分成两半。
我们进一步划分这些数组,我们实现原子价值,不能再划分。
现在,我们以完全相同的方式将它们组合在一起。 请注意这些列表的颜色代码。
我们首先比较每个列表的元素,然后以排序的方式将它们组合到另一个列表中。 我们看到14和33处于排序位置。 我们比较27和10并且在2个值的目标列表中我们首先放置10个,然后是27.我们改变19和35的顺序,而顺序地放置42和44。
在组合阶段的下一次迭代中,我们比较两个数据值的列表,并将它们合并到找到的数据值列表中,所有这些值都按排序顺序排列。
在最终合并之后,列表应如下所示 -
现在我们应该学习合并排序的一些编程方面。
算法 (Algorithm)
合并排序继续将列表分成相等的一半,直到它不再被分割。 根据定义,如果列表中只有一个元素,则对其进行排序。 然后,合并排序组合较小的排序列表,同时保持新列表的排序。
<b>Step 1</b> − if it is only one element in the list it is already sorted, return.
<b>Step 2</b> − divide the list recursively into two halves until it can no more be divided.
<b>Step 3</b> − merge the smaller lists into new list in sorted order.
伪代码 (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编程语言中的合并排序实现,请单击此处 。