C 语言三向归并排序

本文讨论了 C 语言中实现 3 路归并排序的 3 种方法。在归并排序中，数组被递归地分成两部分，排序，最后合并。

归并排序的一种变体是 3 路归并排序，它将数组分成三部分而不是两部分。归并排序将数组递归地分成两半大小的子数组。同样，3 路归并排序将数组分解成三分之一大小的子数组。

在归并排序中，数组被递归地分成两部分，排序，最后合并。归并排序的一种变体称为 3 路归并排序，它不将数组分成两部分，而是分成三部分。

归并排序的示例： 归并排序的示例如下 -

3 路归并排序的时间复杂度是 nlog3n。

示例 1： 这里，我们给出了一个 C 语言中 3 路归并排序的示例。示例如下 -

结果： 现在我们编译上面的程序，成功编译后运行它。然后结果如下 -

The result after the three way of merge sort is: -56 -9 -4 4 8 10 20 29 46 55 67 70 78 85 90

上面的代码是如何工作的？

这里我们首先将统计数组的内容复制到另一个名为 fArr 的数组中。然后通过找到将数组分成三个元素的中间点并对每个数组调用类型特性来对数组进行排序。递归的基本情况是当数组大小为 1 时，它从函数返回。然后数组合并开始，最后，排序后的数组在 fArr 中并复制到 gArr。

归并排序的时间复杂度

3 路归并排序方程为：T(n) = 2T(n/2) + O(n)

同样，对于 3 路归并排序，我们有：T(n) = 3T(n/3) + O(n)

使用主方法求解，其复杂度为 O(n log 3n)。

时间复杂度看起来比 2 路归并排序少，但归并函数中比较次数越多，实践中可能花费的时间就越多。

因此，在本文中，我们简要讨论了 C 语言中 3 路归并排序的 3 种方法。归并排序的一种变体是 3 路归并排序，它将数组分成三部分而不是两部分。我们还给出了一个与此主题相关的示例。