三路归并排序（附C++和Java代码）

ゝ一纸荒年。 2023-07-16 15:54 1阅读 0赞

# 三路归并排序（附C++和Java代码） #

### 文章目录 ###

*  三路归并排序（附C++和Java代码）
 *   *   *   *  C++代码：
             *  Java代码：

**PS**：阅读此文章需了解归并排序基本原理和二路归并排序

三路归并，即：将待排序数组等分为三个部分，然后一直分解到能直接求解为止（也就是分解到一个一个元素）；最后自底向上逐一归并，直至最终合并为一个数组为止

对于大量数据，虽然三路归并比二路归并排序时间复杂度有所下降，但数量级仍为O(nlogn)；空间复杂度也与二路归并一样O(n)

**具体实现代码：**

#### C++代码： ####

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+10;
    int a[maxn],b[maxn];
    void Merge(int a[],int b[],int s,int mid,int midmid,int e){
        
        int i=s,j=mid+1,k=midmid+1;
        int t=i;
        while(i<=mid&&j<=midmid&&k<=e){
        
            if(a[i]<=a[j]&&a[i]<=a[k]){
        
                b[t++]=a[i++];
            }
            else if(a[j]<=a[k]&&a[j]<=a[i]){
        
                b[t++]=a[j++];
            }
            else{
        
                b[t++]=a[k++];
            }
        }
        while(i<=mid&&j<=midmid){
        
            if(a[i]<=a[j]){
        
                b[t++]=a[i++];
            }
            else{
        
                b[t++]=a[j++];
            }
        }
        while(j<=midmid&&k<=e){
        
            if(a[j]<=a[k]){
        
                b[t++]=a[j++];
            }
            else{
        
                b[t++]=a[k++];
            }
        }
        while(k<=e&&i<=mid){
        
            if(a[k]<=a[i]){
        
                b[t++]=a[k++];
            }
            else{
        
                b[t++]=a[i++];
            }
        }
        while(i<=mid){
        
            b[t++]=a[i++];
        }
        while(j<=midmid){
        
            b[t++]=a[j++];
        }
        while(k<=e){
        
            b[t++]=a[k++];
        }
    }
    void mergeSort(int a[],int s,int e){
        
        if(s<e){
        
            int mid=s+(e-s)/3;
            int midmid=e-(e-s)/3;
            mergeSort(a,s,mid);
            mergeSort(a,mid+1,midmid);
            mergeSort(a,midmid+1,e);
            Merge(a,b,s,mid,midmid,e);
            for(int i=s;i<=e;i++){
        
                a[i]=b[i];
            }
        }
    }
    int main(){
        
        int n;
        //表示待排序数组大小
        cin>>n;
        //输入待排序数组
        for(int i=1;i<=n;i++){
        
            cin>>a[i];
        }
        mergeSort(a,1,n);
    
        //返回结果
        cout<<a[1];
        for(int i=2;i<=n;i++){
        
            cout<<" "<<a[i];
        }
        cout<<endl;
        return 0;
    }

#### Java代码： ####

import java.util.*;
    
    public class Main {
        
        public static int[] a=new int[100010];
        public static int[] b=new int[100010];
        public static void merge(int a[],int b[],int s,int mid,int midmid,int e){
        
            int i=s,j=mid+1,k=midmid+1;
            int t=s;
            while (i<=mid&&j<=midmid&&k<=e){
        
                if(a[i]<=a[j]&&a[i]<=a[k]){
        
                    b[t++]=a[i++];
                }
                else if(a[j]<=a[k]&&a[j]<=a[i]){
        
                    b[t++]=a[j++];
                }
                else{
        
                    b[t++]=a[k++];
                }
            }
            while (i<=mid&&j<=midmid){
        
                if(a[i]<=a[j]){
        
                    b[t++]=a[i++];
                }
                else{
        
                    b[t++]=a[j++];
                }
            }
            while (j<=midmid&&k<=e){
        
                if(a[i]<=a[k]){
        
                    b[t++]=a[i++];
                }
                else{
        
                    b[t++]=a[k++];
                }
            }
            while (k<=e&&i<=mid){
        
                if(a[k]<=a[i]){
        
                    b[t++]=a[k++];
                }
                else{
        
                    b[t++]=a[i++];
                }
            }
            while (i<=mid){
        
                b[t++]=a[i++];
            }
            while (j<=midmid){
        
                b[t++]=a[j++];
            }
            while (k<=e){
        
                b[t++]=a[k++];
            }
        }
        public  static void mergeSort(int a[],int s,int e){
        
            if(s<e){
        
                int mid=s+(e-s)/3;
                int midmid=e-(e-s)/3;
                mergeSort(a,s,mid);
                mergeSort(a,mid+1,midmid);
                mergeSort(a,midmid+1,e);
                merge(a,b,s,mid,midmid,e);
                for(int i=s;i<=e;i++){
        
                    a[i]=b[i];
                }
            }
        }
        public static void main(String args[]){
        
            Scanner scan=new Scanner(System.in);
            //输入待排序数组的大小
            int n=scan.nextInt();
            //输入待排序数组
            for(int i=1;i<=n;i++){
        
                a[i]=scan.nextInt();
            }
            mergeSort(a,1,n);
    
            //返回结果
            System.out.print(a[1]);
            for(int i=2;i<=n;i++){
        
                System.out.print(" "+a[i]);
            }
            System.out.println();
        }
    }