如何实现3路合并排序（代码和算法实现）

本文概述

建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
C ++
Java

先决条件–合并排序
合并排序包括将数组递归拆分为两部分, 进行排序, 最后将它们合并。合并排序的一种变体称为3向合并排序, 其中不是将数组拆分为2部分, 而是将其拆分为3部分。
合并排序以递归方式将数组分解为大小为一半的子数组。同样, 三向合并排序会将数组分解为大小为三分之一的子数组。
例子：

Input: 45, -2, -45, 78, 30, -42, 10, 19 , 73, 93 Output : -45 -42 -2 10 19 30 45 73 78 93 Input: 23, -19Output : -1923

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。C ++

// C++ Program to perform 3 way Merge Sort #include < bits/stdc++.h> using namespace std; /* Merge the sorted ranges [low, mid1), [mid1, mid2) and [mid2, high) mid1 is first midpoint index in overall range to merge mid2 is second midpoint index in overall range to merge*/ void merge( int gArray[], int low, int mid1, int mid2, int high, int destArray[]) { int i = low, j = mid1, k = mid2, l = low; // choose smaller of the smallest in the three ranges while ((i < mid1) & & (j < mid2) & & (k < high)) { if (gArray[i] < gArray[j]) { if (gArray[i] < gArray[k]) { destArray[l++] = gArray[i++]; } else { destArray[l++] = gArray[k++]; } } else { if (gArray[j] < gArray[k]) { destArray[l++] = gArray[j++]; } else { destArray[l++] = gArray[k++]; } } } // case where first and second ranges // have remaining values while ((i < mid1) & & (j < mid2)) { if (gArray[i] < gArray[j]) { destArray[l++] = gArray[i++]; } else { destArray[l++] = gArray[j++]; } } // case where second and third ranges // have remaining values while ((j < mid2) & & (k < high)) { if (gArray[j] < gArray[k]) { destArray[l++] = gArray[j++]; } else { destArray[l++] = gArray[k++]; } } // case where first and third ranges have // remaining values while ((i < mid1) & & (k < high)) { if (gArray[i] < gArray[k]) { destArray[l++] = gArray[i++]; } else { destArray[l++] = gArray[k++]; } } // copy remaining values from the first range while (i < mid1) destArray[l++] = gArray[i++]; // copy remaining values from the second range while (j < mid2) destArray[l++] = gArray[j++]; // copy remaining values from the third range while (k < high) destArray[l++] = gArray[k++]; } /* Performing the merge sort algorithm on the given array of values in the rangeof indices [low, high). low is minimum index, high is maximum index (exclusive) */ void mergeSort3WayRec( int gArray[], int low, int high, int destArray[]) { // If array size is 1 then do nothing if (high - low < 2) return ; // Splitting array into 3 parts int mid1 = low + ((high - low) / 3); int mid2 = low + 2 * ((high - low) / 3) + 1; // Sorting 3 arrays recursively mergeSort3WayRec(destArray, low, mid1, gArray); mergeSort3WayRec(destArray, mid1, mid2, gArray); mergeSort3WayRec(destArray, mid2, high, gArray); // Merging the sorted arrays merge(destArray, low, mid1, mid2, high, gArray); }void mergeSort3Way( int gArray[], int n) { // if array size is zero return null if (n == 0) return ; // creating duplicate of given array int fArray[n]; // copying alements of given array into // duplicate array for ( int i = 0; i < n; i++) fArray[i] = gArray[i]; // sort function mergeSort3WayRec(fArray, 0, n, gArray); // copy back elements of duplicate array // to given array for ( int i = 0; i < n; i++) gArray[i] = fArray[i]; } // Driver Code int main() { int data[] = {45, -2, -45, 78, 30, -42, 10, 19, 73, 93}; mergeSort3Way(data, 10); cout < < "After 3 way merge sort: " ; for ( int i = 0; i < 10; i++) { cout < < data[i] < < " " ; } return 0; }// This code is contributed by Rashmi Kumari

Java

// Java program to perform 3 way Merge Sort import java.util.*; public class MergeSort3Way { // Functionfor 3-way merge sort process public static void mergeSort3Way(Integer[] gArray) { // if array of size is zero returns null if (gArray == null ) return ; // creating duplicate of given array Integer[] fArray = new Integer[gArray.length]; // copying alements of given array into // duplicate array for ( int i = 0 ; i < fArray.length; i++) fArray[i] = gArray[i]; // sort function mergeSort3WayRec(fArray, 0 , gArray.length, gArray); // copy back elements of duplicate array // to given array for ( int i = 0 ; i < fArray.length; i++) gArray[i] = fArray[i]; }/* Performing the merge sort algorithm on the given array of values in the rangeof indices [low, high).low is minimum index, high is maximum index (exclusive) */ public static void mergeSort3WayRec(Integer[] gArray, int low, int high, Integer[] destArray) { // If array size is 1 then do nothing if (high - low < 2 ) return ; // Splitting array into 3 parts int mid1 = low + ((high - low) / 3 ); int mid2 = low + 2 * ((high - low) / 3 ) + 1 ; // Sorting 3 arrays recursively mergeSort3WayRec(destArray, low, mid1, gArray); mergeSort3WayRec(destArray, mid1, mid2, gArray); mergeSort3WayRec(destArray, mid2, high, gArray); // Merging the sorted arrays merge(destArray, low, mid1, mid2, high, gArray); }/* Merge the sorted ranges [low, mid1), [mid1, mid2) and [mid2, high) mid1 is first midpoint index in overall range to merge mid2 is second midpoint index in overall range to merge*/ public static void merge(Integer[] gArray, int low, int mid1, int mid2, int high, Integer[] destArray) { int i = low, j = mid1, k = mid2, l = low; // choose smaller of the smallest in the three ranges while ((i < mid1) & & (j < mid2) & & (k < high)) { if (gArray[i].compareTo(gArray[j]) < 0 ) { if (gArray[i].compareTo(gArray[k]) < 0 ) destArray[l++] = gArray[i++]; else destArray[l++] = gArray[k++]; } else { if (gArray[j].compareTo(gArray[k]) < 0 ) destArray[l++] = gArray[j++]; else destArray[l++] = gArray[k++]; } }// case where first and second ranges have // remaining values while ((i < mid1) & & (j < mid2)) { if (gArray[i].compareTo(gArray[j]) < 0 ) destArray[l++] = gArray[i++]; else destArray[l++] = gArray[j++]; }// case where second and third ranges have // remaining values while ((j < mid2) & & (k < high)) { if (gArray[j].compareTo(gArray[k]) < 0 ) destArray[l++] = gArray[j++]; else destArray[l++] = gArray[k++]; }// case where first and third ranges have // remaining values while ((i < mid1) & & (k < high)) { if (gArray[i].compareTo(gArray[k]) < 0 ) destArray[l++] = gArray[i++]; else destArray[l++] = gArray[k++]; }// copy remaining values from the first range while (i < mid1) destArray[l++] = gArray[i++]; // copy remaining values from the second range while (j < mid2) destArray[l++] = gArray[j++]; // copy remaining values from the third range while (k < high) destArray[l++] = gArray[k++]; }// Driver function public static void main(String args[]) { // test case of values Integer[] data = https://www.lsbin.com/new Integer[] { 45 , - 2 , - 45 , 78 , 30 , - 42 , 10 , 19 , 73 , 93 }; mergeSort3Way(data); System.out.println("After 3 way merge sort: " ); for ( int i = 0 ; i < data.length; i++) System.out.print(data[i] + " " ); } }

输出如下：

After 3 way merge sort: -45 -42 -2 10 19 30 45 73 78 93

在这里, 我们首先将数据数组的内容复制到另一个名为fArray的数组。然后, 通过找到将数组分为三部分的中点对数组进行排序, 并分别在每个数组上调用sort函数。递归的基本情况是当数组的大小为1且从函数返回时。然后开始合并数组, 最后将排序后的数组放入fArray中, 然后将其复制回gArray。
时间复杂度
：在进行2路合并排序的情况下, 我们得到以下公式：T(n)= 2T(n / 2)+ O(n)
类似地, 在三向合并排序的情况下, 我们得到以下等式：T(n)= 3T(n / 3)+ O(n)
通过使用解决
主法
, 我们得到它的复杂性
O(n对数
3
【如何实现3路合并排序（代码和算法实现）】n)。
。尽管与
2路合并排序
, 由于合并功能中的比较次数会增加, 因此实际花费的时间可能会更长。请参考
为什么二元搜索优于三元搜索？
有关详细信息。
类似文章：
3种快速排序
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。