以下代码是根据 CLRS ( Corman, Leiserson, Rivest, Stein — 'Introduction to Algorithms' ) 教科书进行归并排序的。
我无法确定正在发生的错误,尽管我知道 mergesort()
函数中发生了一些错误。我认为 merge()
在功能上是完整的。
/* Merge sort as per CLRS */
#include <stdio.h>
#include <stdlib.h>
void merge(int *a,int p,int q,int r){
int n1 = q - p + 1;
int n2 = r - q;
int* l = malloc((n1+1)*sizeof(int));
int* ri = malloc((n2+1)*sizeof(int));
int i,j;
for(i = 0 ; i < n1 ; i++)
l[i] = a[p+i-1];
for(i = 0 ; i < n2 ; i++)
ri[i] = a[q+i];
l[n1] = 9999;
ri[n2] = 9999;
i = 0;
j = 0;
int k;
for ( k = p ; k <= r ; k++){
if( l[i] < ri[j] ){
a[k] = l[i];
i++;
}
else{
a[k] = ri[j];
j++;
}
}
}
void mergeSort(int* a,int p,int r){
if( p < r){
int q = ( p + r ) / 2;
mergeSort(a,p,q);
mergeSort(a,p+1,r);
merge(a,p,q,r);
}
else return;
}
int main(int argc, char* argv[]){
int a[] = {9,21,4,15,1,3};
mergeSort(a,0,5);
int i;
for( i = 0 ; i < 6 ; i++){
printf("%d ",a[i]);
}
return 0;
}
最佳答案
void merge(int *a,int p,int q,int r){
int n1 = q - p + 1;
int n2 = r - q;
int* l = malloc((n1+1)*sizeof(int));
int* ri = malloc((n2+1)*sizeof(int));
int i,j;
for(i = 0 ; i < n1 ; i++)
l[i] = a[p+i-1];
for(i = 0 ; i < n2 ; i++)
ri[i] = a[q+i];
您正在编写从索引 p-1
到索引 q-1
到 l
的元素,以及从索引 的元素q
到 r-1
到 ri
。如果 p == 0
,则您访问越界。
但是,您希望对从索引 p
到 r
的元素进行排序。
void merge(int *a,int p,int q,int r){
int n1 = q - p + 1;
int n2 = r - q;
int* l = malloc((n1)*sizeof(int));
int* ri = malloc((n2)*sizeof(int));
int i,j;
for(i = 0 ; i < n1 ; i++)
l[i] = a[p+i];
for(i = 0 ; i < n2 ; i++)
ri[i] = a[q+i+1];
此外,您应该检查两个索引 i
和 j
是否小于相应的结束索引 n1
resp。 n2
,当一个到达其部分的末尾时,将另一部分的剩余部分复制到数组中。如果数组包含大量条目,则保护值会严重失败。
while(i < n1 && j < n2) {
if (ri[j] < l[i]) {
a[k++] = ri[j++];
} else {
a[k++] = l[i++];
}
}
while(i < n1) {
a[k++] = l[i++];
}
while(j < n2) {
a[k++] = ri[j++];
}
关于c - 基于CLRS教科书的归并排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14243232/