3 路归并排序 C 程序

Question

我试图为学校项目“升级”我的正常合并排序。但我的新代码似乎没有像它应该的那样配合

所以我有一个 MergeSort3way 函数，它将输入的数组拆分为 3 个子数组，然后它调用自身直到排序完成，但输出远远不正确。

void Mergesort3way(int A[],int n){
//Sort array A with divition of 3
int B[n/3];
int C[n/3];
int D[n/3];
int i,c;

if(n>1){
    for(i=0;i<n/3;i++){
        B[i]=A[i];
    }
    for(i=n/3;i<2*n/3;i++){
        c= i-n/3;
        C[c]=A[i];
    }
    for(i=2*n/3;i<n;i++){
        c=i-(2*n/3);
        D[c]=A[i];
    }

Mergesort3way(B,n/3);
Mergesort3way(C,n/3);
Mergesort3way(D,n/3);
int bn = sizeof(B)/sizeof(B[0]);
int cn = sizeof(C)/sizeof(C[0]);
int dn = sizeof(D)/sizeof(D[0]);
Merge3way(B,C,D,A,bn,cn,dn);    
}

}

之后 merge3way 将它们组合成 1 个排序数组

void Merge3way(int B[],int C[],int D[],int A[],int p,int q,int r){
int i=0,j=0,u=0,k=0;

while(i<p && j<q && u<r){
    if(B[i]<C[j]){
        if(B[i]<D[u]){
            A[k]=D[u];
            u++;
        }else{
            A[k]=B[i];
            i++;
        }
    }else{
        if(C[j]<D[u]){
          A[k]=D[u];
          u++;  
        }else{
          A[k]=C[j];
          j++;
        }
    }
    k++;
 }
int all = p+q+r;    
if(i==p){
    if(u==r){
     while(j<q && k<all){
        A[k]=C[j];
        k++;
        j++;            
     } 
    }else{
        while(u<r && k<all){
        A[k]=D[u];
        k++;
        u++;
        }
    }
}else if(j==q){
    if(u==r){
     while(i<p && k<all){
        A[k]=B[i];
        k++;
        i++;            
     } 
}
  }
} 

你能给我建议任何解决方案吗，这样我就可以排序，我已经尝试了两个多小时的修改，结果总是一样的。预先感谢，请不要感到难受，因为这是我第一次使用该网站。

Answer 1

如果这应该是升序排序，那么 if (B[i] < C[j]) && (B[i] < D[u]), the code should do A[k] = B[i].

一旦到达 B[]、C[] 或 D[] 的末尾，代码需要切换到对剩余两个进行 2 路合并。您可以交换数组名称（它们实际上是被调用函数中的指针），以简化此操作，因此 2 路合并使用 B 和 C。如果首先到达 B 的末尾，则 B = C 且 C = D。首先到达 C 的末尾，则 C = D。如果先到达 D 的末尾，则不需要数组（指针）赋值。

一旦到达 B 或 C 的末尾，则只需复制剩余的子数组即可。

为了索引上的命名一致，我会使用 k 表示 D[]，使用 u 表示 A[]，但这不会造成问题。

Answer 2

我认为你的代码的这一部分，

while(i<p && j<q && u<r){
    if(B[i]<C[j]){
        if(B[i]<D[u]){
            A[k]=D[u];
            u++;
        }else{
            A[k]=B[i];
            i++;
        }
    }else{
        if(C[j]<D[u]){
          A[k]=D[u];
          u++;  
        }else{
          A[k]=C[j];
          j++;
        }
    }
    k++;
 }

需要更改为：

while(i<p && j<q && u<r){
    if(B[i]<C[j]){
        if(B[i]<D[u]){
            A[k]=B[i];
            i++;
        }else{
            A[k]=D[u];
            u++;
        }
    }else{
        if(C[j]<D[u]){
          A[k]=C[j];
          j++;  
        }else{
          A[k]=D[u];
          u++;
        }
    }
    k++;
 }

这部分代码：

if(i==p){
    if(u==r){
     while(j<q && k<all){
        A[k]=C[j];
        k++;
        j++;            
     } 
    }else{
        while(u<r && k<all){
        A[k]=D[u];
        k++;
        u++;
        }
    }
}else if(j==q){
    if(u==r){
     while(i<p && k<all){
        A[k]=B[i];
        k++;

需要更改为一些，如下所示：

if (i < p && j < q){
  # append the result of normal merge of remaining elements of B and C to A
} else if (j < q && u < r) {
  # append the result of normal merge of remaining elements of C and D to A
} else if (i < p && u < r) {
  # append the result of normal merge of remaining elements of B and D to A
} else {
      if (i == p && j == q && u < r){
         # append remaining elements of D to A
      } else if (i < p && j == q && u == r){
         # append remaining elements of B to A
      } else if (i == p && j < q && u == r){
         # append remaining elements of C to A
      }
}

虽然，正如您所说，您有一个正在尝试修改的

normal mergesort

，但是，如果在对数组的每个

1/3

rd 部分进行排序之后怎么样，如下所示：

Mergesort3way(B,n/3);
Mergesort3way(C,n/3);
Mergesort3way(D,n/3);

首先使用

normal mergesort

将两个排序部分中的任何一个组合起来，然后使用

normal mergesort

再次将它们的结果与第三部分组合起来。例如：首先使用

sorted B

将

sorted C

与

normal mergesort

合并，我们将其结果称为

BmC

，然后使用

BmC

将其结果

sorted D

与

normal mergesort

合并，最终得到合并结果：

BmCmD 

.