在上一篇文章中，我们熟悉了遗留合并排序 （主要引起历史兴趣）。 今天的趋势是什么？

为了使您熟悉通过合并进行排序的概念，通常使用平衡合并算法。 术语“平衡”是指算法将数组及其子数组递归地拆分为大致相等的部分。 今天，我们看看它在实践中的外观。

两种方法的一对功能相同。 无论如何，“上下”，“上下”几乎是相同的算法，只是从不同的角度显示。

实际上，我们需要将该段的两半合并为一个子数组。 将这两个半部分同时排列在一个数组中，比较两次迭代中的当前元素，将较小的元素放入第二个数组中：

//   A[iBegin: iMiddle - 1] //   A[iMiddle: iEnd - 1] //:   B[iBegin: iEnd - 1] void Merge(A[], iBegin, iMiddle, iEnd, B[]) { i = iBegin, j = iMiddle; //       ... for (k = iBegin; k < iEnd; k++) { //     //  <=    if (i < iMiddle && (j >= iEnd || A[i] <= A[j])) { B[k] = A[i]; i++; } else { B[k] = A[j]; j++; } } } 

将段从一个数组复制到另一个数组。 两种实现都在两个阵列上运行，数据必须不断地从主驱动到辅助，反之亦然：

 //    A[] //   B[] void CopyArray(A[], iBegin, iEnd, B[]) { for(k = iBegin; k < iEnd; k++) B[k] = A[k]; } 

降序兼并

首先，获取整个数组，然后开始递归下降。 将数组二分，直到我们到达一个元素的子数组（由它们自己排序）。 然后递归开始反向上升，沿途合并子数组（子数组的大小在每个级别加倍）。

 //  A[]     // B[]   void TopDownMergeSort(A[], B[], n) { CopyArray(A, 0, n, B); // A[]  B[] TopDownSplitMerge(B, 0, n, A);// B[]    A[] } //    A[],  B[]    // : iBegin ; iEnd   void TopDownSplitMerge(B[], iBegin, iEnd, A[]) { // size == 1,     if(iEnd - iBegin < 2) return; // size > 1,     iMiddle = (iEnd + iBegin) / 2;//iMiddle -   //     A[]  B[] TopDownSplitMerge(A, iBegin, iMiddle, B);//   TopDownSplitMerge(A, iMiddle, iEnd, B);//   //    B[]  A[] Merge(B, iBegin, iMiddle, iEnd, A); } 

均衡向上合并

在此，我们首先沿相邻的最小数组（来自一个元素）对数组进行迭代，然后成对合并。 在每个步骤中将排序后的子数组加倍后，我们再次合并邻居并继续，直到在输出中获得排序后形式的整个数组为止。

 //  A[]     // B[]   void BottomUpMergeSort(A[], B[], n) { //      A[]  «». //    : //× 2, 4, 8, 16, ... -   ,       for (width = 1; width < n; width = 2 * width) { //     width for (i = 0; i < n; i = i + 2 * width) { //   : //A [i: i + width - 1]  A [i + width: i + 2 * width - 1]  B[] //  A[i: n - 1]  B[] ( i + width > = n) Merge(A, i, min(i + width, n), min(i + 2 * width, n), B); } //   B[]    2 * width //  B[]   A[]    //     A[]  B[] CopyArray(B, 0, n, A); // B[]  A[] //      2 * width } } 

通常，自上而下的实现是可取的，因为它更有效地使用两个数组，这些数组不断地更改“主/辅助”的角色。 在上游版本中，阵列A始终是主阵列，阵列B始终是辅助阵列。 结果，在每次迭代之后，来自B的数据必须全部返回给A，这不会有助于算法复杂度的提高。 另一方面，上升的实现更简单；它甚至没有递归。

不平衡合并

从“平衡”一词本身可以看出某种可靠性，稳定性。 您甚至可能会觉得必须平衡好的算法。 而且“不平衡”与某种程度的晃动和扭曲有关。 好吧，真的， 不平衡的人在所有方面都比不平衡的人好吗？

实际上，情况更糟。 当然，将子数组划分为相等的两部分（这意味着合并排序的平衡）更容易实现。 将数组分成两半，然后对每一半递归。 实际上，这种轻松是平衡并购之前的主要优势。

在以下出版物中，我们将介绍不平衡的方法。 它们明显更难于理解和实施。 用于后续合并的数据将不会在辅助阵列中平均分配，而是根据多个广义斐波纳契数进行分配。 这将使您获得强大的结果，这是简化的平衡方法无法实现的。

参考文献

合并 （ Google-translate ）， 合并

系列文章：

• Excel应用程序AlgoLab.xlsm
• 交换排序
• 插入排序
• 按选择排序
• 合并排序
  
  • 自上而下和自下而上的平衡兼并
  • 多相合并排序
  • 级联合并排序
  • 振荡合并排序
  • 线程化和不混溶的排序
  • 合并排序比较
• 按分布排序
• 混合排序

现在，AlgoLab应用程序中将提供下一个合并排序（对于那些使用此Excel应用程序研究算法的人，请更新文件）。

数组受到临时限制-数组的大小必须为2的幂（由于编程可视化时会遇到一些困难）。 稍后，可以对任何数组进行排序。

本文是在EDISON Software的支持下撰写的，EDISON Software是一家使用云服务来创建嵌入式软件并在JAVA上开发移动应用程序的公司 。