数据结构和合并排序算法 数据结构和算法选择排序 数据结构和算法Shell排序 合并排序是一种基于分而治之技术的排序技术。在最坏情况下的时间复杂度为0(n log n)时，它是最受尊敬的算法之一。 合并排序首先将数组分成相等的一半，然后以排序的方式组合它们。 合并排序如何工作？ 要理解合并排序，我们采用未排序的数组，如下所示 - 我们知道，除非实现原子值，否则合并排序首先将整个数组迭代地分成相等的一半。我们在这里看到，8个项目的数组被分成两个大小为4的数组。 这不会改变原始项目的外观顺序。现在我们将这两个数组分成两半。 我们进一步划分这些数组，我们实现原子价值，不能再划分。 现在，我们以完全相同的方式将它们组合在一起。请注意这些列表的颜色代码。 我们首先比较每个列表的元素，然后以排序的方式将它们组合到另一个列表中。我们看到14和33处于排序位置。我们比较27和10并且在2个值的目标列表中我们首先放置10个，然后是27.我们改变19和35的顺序，而顺序地放置42和44。 在组合阶段的下一次迭代中，我们比较两个数据值的列表，并将它们合并到找到的数据值列表中，将所有数据值排序。 在最终合并之后，列表应该如下所示 - 现在我们应该学习合并排序的一些编程方面。 算法 合并排序继续将列表分成相等的一半，直到它不再被分割。根据定义，如果列表中只有一个元素，则对其进行排序。然后，合并排序组合较小的排序列表，同时保持新列表的排序。 **Step 1** − if 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 数据结构和算法选择排序 数据结构和算法Shell排序
