如何使用合并排序对具有结构条目的数组进行排序？

Question

这是我为

mergesort

功能编写的代码

void mergesort(struct record *record_arr, int low, int high) {
    if (low >= high) {
        return;
    }
    int mid = (low + high) / 2;
    mergesort(record_arr, low, mid);
    mergesort(record_arr, mid + 1, high);
    merge(record_arr, low, mid, high);
}

void merge(struct record *record_arr, int low, int mid, int high) {
    int i, j, k;
    int n1 = mid - low + 1;
    int n2 = high - mid;
    struct record *tmp1 = (struct record *)allocate_memory((n1 + 1) * sizeof(struct record));
    struct record *tmp2 = (struct record *)allocate_memory((n2 + 1) * sizeof(struct record));
    for (i = 0; i <= n1; i++) {
        tmp1[i] = record_arr[low + i];
    }
    for (j = 0; j <= n2; j++) {
        tmp2[j] = record_arr[mid + 1 + j];
    }
    tmp1[i + 1] = (struct record){ 0 };
    tmp2[j + 1] = (struct record){ 0 };
    i = j = 0;
    for (k = low; k <= high; k++) {
        if ((cmp_record(tmp1 + i, tmp2 + j) == 0) || (cmp_record(tmp1 + i, tmp2 + j) == -1)) {
            record_arr[k] = tmp1[i];
            i++;
        } else {
            record_arr[k] = tmp2[j];
            j++;
        }
    }
    //for (k = low; k <= high; k++) {
    //    if ((cmp_uid(tmp1[i].uid, tmp2[j].uid)) == 0 || (cmp_uid(tmp1[i].uid, tmp2[j].uid)) == -1) {
    //        record_arr[k] = tmp1[i];
    //        i++;
    //    } else {
    //        record_arr[k] = tmp2[j];
    //        j++;
    //    }
    //}
}

问题中已经给出了结构记录和

cmp_uid

，

cmp_record

，

allocate_memory

等功能。数组必须根据

uid

进行排序，即

char

。

cmp_uid

的功能就像

strcmp

，对于

allocate_memory

，它就像

malloc

。实施后，数组未排序，我收到此错误

:~/DSALAB/PA1$ make
gcc -g -Werror -shared -O3 -fPIC -o libpa1.so pa1.c
gcc -g -Werror -O3 -L. -Wl,-rpath=. -o test1 test1.c -ldsa -lpa1 -lm
gcc -g -Werror -O3 -L. -Wl,-rpath=. -o test2 test2.c -ldsa -lpa1 -lm
gcc -g -Werror -O3 -L. -Wl,-rpath=. -o test3 test3.c -ldsa -lpa1 -lm
:~/DSALAB/PA1$ ./test2 10

Running TEST2 for 10 inputs
Creating 10 uids took 0 ms.
adding 10 records took 0 ms.
linear search 10 records took 0 ms.
quick sort 10 records took 0 ms.
binary search 10 records took 0 ms.
inserting 10 records took 0 ms.
array is not sorted
test2: lib.c:527: check_array_is_sorted_by_uid: Assertion `0' failed.
Aborted

Answer 1

您的实现依赖于一种称为 sentinels 的容易出错的技术，其中将已知大于所有有效值的值插入到切片的末尾。这不是一个好主意，您应该比较索引值并且只比较切片内部的结构。

还请注意，只有左切片需要保存，右切片中的结构在比较之前永远不会被覆盖。

为副本分配的内存必须在

merge

函数结束时释放，否则内存将丢失。

Answer 2

void merge(struct record* record_arr,int low, int mid,int high){
  int i,j,k;
  int n1=mid-low+1;
  int n2=high-mid;
  struct record* tmp1=(struct record*)allocate_memory((n1+1)*sizeof(struct record));
  struct record* tmp2=(struct record*)allocate_memory((n2+1)*sizeof(struct record));
  for (i=0;i<n1;i++){
    tmp1[i]=record_arr[low+i];
  }
  for (j=0;j<n2;j++){
    tmp2[j]=record_arr[mid+1+j];
  }
  tmp1[n1]=(struct record){0};
  tmp2[n2]=(struct record){0};
  i=j=0;
  for (k=low;k<=high;k++){
    if ((cmp_record(tmp1+i,tmp2+j)==0) || (cmp_record(tmp1+i,tmp2+j)==-1)){
      record_arr[k]=tmp1[i];
      i++;
    }else{
      record_arr[k]=tmp2[j];
      j++;
    }
    if (tmp1[i].uid == NULL) {
        while (j < n2) {
            k++;
            record_arr[k] = tmp2[j];
            j++;
        }
        break;
    } else if (tmp2[j].uid == NULL) {
        while (i < n1) {
            k++;
            record_arr[k] = tmp1[i];
            i++;
        }
        break;
    }
  }
}