时间戳

首页 > 解决方案 > C. 双向合并。计算比较

c - C. 双向合并。计算比较

问题描述

一切似乎都正常工作。但我需要再次计算比较。出于某种原因，当我尝试实现它时，该程序拒绝工作。而在过去（我的意思是过去的排序），我计算了交换......好吧，据我所知，这种排序中没有交换，所以当我们重写到另一个数组时，我们需要计算，对吧？请帮我计算一下。最好立即使用代码。提前谢谢您。

#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;
}

标签： csortingmergemergesort

解决方案

您的代码中有细微的错误。但是下面的代码应该可以正常工作。

#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);

推荐阅读