1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 using namespace std;  5   6 #define N 100005  7 int a[N],b[N],c[N];  8   9 //这个函数不断用来找三段区域中的最小值的那个点，以便用来将找到的点存入b数组中 10 int minn(int i,int j,int l) 11 { 12     if(a[i]<a[j]&&a[i]<a[l]) 13         return 1; 14     else if(a[j]<a[i]&&a[j]<a[l]) 15         return 2; 16     else 17         return 3; 18 } 19 //每次合并三个区域后，一个区域率先完成，那接下来两个区域继续合并就用下面这个函数 20 void mergeTwoArray(int st1,int la1 , int st2, int la2 ,int k,int *a,int *b) 21 { 22     int i = st1,j=st2; 23     while(i<=la1&&j<=la2){ 24         if(a[i]<a[j]) 25             b[k++] = a[i++]; 26  27         else 28             b[k++] = a[j++]; 29     } 30     if(i<=la1) 31         while(i<=la1) 32             b[k++] = a[i++]; 33     if(j<=la2) 34         while(j<=la2) 35             b[k++] = a[j++]; 36 } 37 //合并三段区域的过程 38 void mov(int x,int m,int n,int y,int *a,int *b) 39 { 40     int i=x,j=m+1,l=n+1,k=x; 41     while(i<=m&&j<=n&&l<=y){ 42         int t = minn(i,j,l); 43         if(t == 1) 44             b[k++] = a[i++]; 45  46         else if(t == 2) 47             b[k++] = a[j++]; 48  49         else 50             b[k++] = a[l++]; 51     } 52  53     if(i>m) 54         mergeTwoArray(j,n,l,y,k,a,b);//说明左侧区域元素用尽，带入参数继续合并其他两个区域，后面else if中的语句也是同一个意思 55     else if(j>n) 56         mergeTwoArray(i,m,l,y,k,a,b); 57     else 58         mergeTwoArray(i,m,j,n,k,a,b); 59 } 60  61 void cpy(int x,int y,int *a,int *b) 62 { 63     for(int i=x;i<=y;i++) 64         a[i] = b[i]; 65 } 66  67 //总的归并过程 68 void mergeSort(int x,int y,int *a) 69 { 70     if(x>=y) 71         return; 72     int thi1 = (y-x)/3+x; 73     int thi2 = y-(y-x)/3; 74     mergeSort(x,thi1,a);//合并最左边 75     mergeSort(thi1+1,thi2,a);//合并中间区域 76     mergeSort(thi2+1,y,a);//合并右侧区域 77  78     //将分割的三块区域不断找到最小值后从a数组移入b数组 79     mov(x,thi1,thi2,y,a,b); 80     //将b数组的元素重新移回a数组 81     cpy(x,y,a,b); 82 } 83  84 int main() 85 { 86     int T; 87     printf("输入测试样例数: "); 88     scanf("%d",&T); 89     while(T--){ 90         int n; 91         printf("输入元素的个数: "); 92         scanf("%d",&n); 93         printf("依次输入所有的元素："); 94         for(int i=0;i<n;i++){ 95             scanf("%d",a+i); 96         } 97         mergeSort(0,n-1,a); 98         printf("输出三分排序后的结果:\n"); 99         for(int i=0;i<n;i++){100             printf("%d ",a[i]);101         }102         puts("");103     }104     return 0;105 }