C.双向merge.Calculate比较
C.双向merge.Calculate比较
提问于 2021-03-28 15:24:29
一切似乎都在正常运行。但我需要再计算一次比较。由于某些原因，当我试图实现它时，程序拒绝工作。在过去的时间(我是指过去的排序)，我计算了swaps..well，据我所知，在这种排序中没有交换，所以当我们重写到另一个数组时，我们需要计数，对吧？请帮我算一下这个。最好是马上与code.Thank提前通知您。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void merge( int *a, int lb, int split, int ub) {
int pos1=lb;
int pos2=split+1;
int pos3=0;
int *temp = (int*)malloc(ub+1 * sizeof(int));
while (pos1 <= split && pos2 <= ub) {
if (a[pos1] <= a[pos2])
temp[pos3++] = a[pos1++];
else
temp[pos3++] = a[pos2++];
}
while (pos2 <= ub)
temp[pos3++] = a[pos2++];
while (pos1 <= split)
temp[pos3++] = a[pos1++];
for (pos3 = 0; pos3 < ub-lb+1; pos3++)
a[lb+pos3] = temp[pos3];
}
void mergeSort(int *a, int lb, int ub) {
long split;
if (lb < ub) {
split = (lb + ub)/2;
mergeSort(a, lb, split);
mergeSort(a, split+1, ub);
merge(a, lb, split, ub);
}
}
void arrprint(int *arr, int n) {
printf("%d", *arr);
int i;
for ( i = 1; i < n; i++) printf(" %d", arr[i]);
puts("");
}
int main(int argc, char *argv[]) {
int n = 10;
int *arr;
arr = malloc(n * sizeof *arr);
srand(time(NULL));
int s;
for ( s = 0; s < n; s++)
arr[s] = rand() % 50;
arrprint(arr, n);
mergeSort(arr, 0, n-1);
arrprint(arr, n);
free(arr);
puts("");
return 0;
}回答 1
Stack Overflow用户
发布于 2021-03-28 16:20:47
您的代码中有一些细微的错误。但是下面的代码应该可以很好地工作。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void merge( int *a, int lb, int split, int ub, int* count) {
int pos1=lb;
int pos2=split+1;
int pos3=0;
int *temp = (int*)malloc((ub+1) * sizeof(int)); // change 5
while (pos1 <= split && pos2 <= ub) {
if (a[pos1] <= a[pos2]){
temp[pos3++] = a[pos1++];
(*count)++;
}
else{
temp[pos3++] = a[pos2++];
(*count)++;
}
}
while (pos2 <= ub)
temp[pos3++] = a[pos2++];
while (pos1 <= split)
temp[pos3++] = a[pos1++];
for (pos3 = 0; pos3 < ub-lb+1; pos3++)
a[lb+pos3] = temp[pos3];
free(temp); // required
}
void mergeSort(int *a, int lb, int ub, int* count) {
long split;
if (lb < ub) {
split = (lb + ub)/2;
mergeSort(a, lb, split, count);
mergeSort(a, split+1, ub, count);
merge(a, lb, split, ub, count);
}
}
void arrprint(int *arr, int n) {
printf("%d", *arr);
int i;
for ( i = 1; i < n; i++) printf(" %d", arr[i]);
puts("");
}
int main(int argc, char *argv[]) {
int n = 10;
int *arr = NULL; // change 1
arr = (int*)malloc(n * sizeof *arr); // change 2
int c = 0; // change 3, c is in stack
int* count = &c; // change 4
srand(time(NULL));
int s;
for ( s = 0; s < n; s++ )
arr[s] = rand() % 50;
arrprint(arr, n);
mergeSort(arr, 0, n-1, count);
arrprint(arr, n);
free(arr);
puts("");
printf("Comparison count: %d\n", *count);
return 0;
}在这里，通过函数调用传递一个额外的int变量来计算比较。
请注意，最佳实践是检查内存是否实际上是由malloc分配的。
arr = (int*)malloc(n * sizeof *arr);
if(arr){
// ...
}
free(arr);页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/66839253
复制相关文章
相似问题
腾讯云开发者
