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

2021年3月21日17:23:52 发表评论 1,006 次浏览

本文概述

先决条件–合并排序

合并排序包括将数组递归拆分为两部分, 进行排序, 最后将它们合并。合并排序的一种变体称为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, -19
Output : -19  23

推荐：请尝试以下方法{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
{
     // Function  for 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 = 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

n)。

。尽管与

2路合并排序

, 由于合并功能中的比较次数会增加, 因此实际花费的时间可能会更长。请参考

为什么二元搜索优于三元搜索？

有关详细信息。

类似文章：

3种快速排序

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: