合并排序结构

#include #include typedef struct points{ float axis[2]; int id; }Points; typedef enum{ SortById, SortByXAxis }SortType; Points* fill_Array(char* filename, int* length); void Print_set(Points* set, int number_of_points); void mergesort(Points* set, int low, int high, int number_of_points,SortType sort); void merge(Points* set, int low, int middle, int high, int number_of_points,SortType sort); int main(int argc, char* argv[]) { int length; Points *array; array=fill_Array(argv[1],&length); Print_set(array,length); printf("\n\n"); mergesort(array,0,length,length,SortById); Print_set(array,length); return 0; } Points* fill_Array(char* filename,int* length) { int i; Points* array; FILE* file=fopen(filename,"r"); if(file == NULL) { return NULL; } fscanf(file,"%d",length); array=malloc(sizeof(Points)* *length); for(i = 0; i id,&(array+i)->axis[0],&(array+i)->axis[1]); } fclose(file); return array; } void Print_set(Points *set, int number_of_points) { int i; for(i = 0; i id,(set+i)->axis[0],(set+i)->axis[1]); } } void mergesort(Points* set,int low,int high,int number_of_points, SortType sort) { int mid1; if((high-low)>=1) { mid1 = (low+high)/2; mergesort(set, low, mid1, number_of_points, sort); mergesort(set, mid1+1, high, number_of_points, sort); merge(set, low, mid1, high, number_of_points, sort); } } void merge(Points* set, int low, int middle, int high, int number_of_points, SortType sort) { int leftIndex=low; int rightIndex=middle; int combinedIndex = low; Points tempArray[number_of_points]; int i; while(leftIndex <= middle && rightIndex<= high) { if(set[leftIndex].id <= set[rightIndex].id) { tempArray[combinedIndex++] = set[leftIndex++]; } else tempArray[combinedIndex++] = set[rightIndex++]; } if(leftIndex == middle+1) { while(rightIndex <= high) { tempArray[combinedIndex++] = set[rightIndex++]; } } else { while(leftIndex <= middle) { tempArray[combinedIndex++] = set[leftIndex++]; } } for( i = low; i < high; i++) { set[i] = tempArray[i]; } } 

我试图使用自定义合并排序function对输入文件执行合并排序。 然而，合并排序function不起作用并在下面打印出来，第一个块是打印出的实际输入文件，以确保fscanf正确读取所有内容，第二个块是在合并function运行后打印。 这些函数复制了一些值，并没有对它们进行排序，我在代码中找不到错误。 请注意，在我使用它来对id或那些值进行排序之前，枚举将用于对id或第一个浮点值进行排序，我只是想让合并排序工作。

 1 13.000000 7.000000 13 14.000000 6.000000 95 7.000000 13.000000 39 0.000000 20.000000 78 10.000000 10.000000 68 3.000000 17.000000 32 6.000000 14.000000 10 19.000000 1.000000 0 18.000000 2.000000 45 17.000000 3.000000 92 4.000000 16.000000 29 5.000000 15.000000 85 8.000000 12.000000 79 15.000000 5.000000 12 16.000000 4.000000 32 1.000000 19.000000 77 9.000000 11.000000 52 12.000000 8.000000 80 11.000000 9.000000 31 2.000000 18.000000 1 13.000000 7.000000 13 14.000000 6.000000 68 3.000000 17.000000 0 18.000000 2.000000 10 19.000000 1.000000 0 18.000000 2.000000 0 18.000000 2.000000 92 4.000000 16.000000 92 4.000000 16.000000 29 5.000000 15.000000 32 1.000000 19.000000 52 12.000000 8.000000 77 9.000000 11.000000 79 15.000000 5.000000 12 16.000000 4.000000 32 1.000000 19.000000 32 1.000000 19.000000 80 11.000000 9.000000 95 7.000000 13.000000 95 7.000000 13.000000 

Answer 1

您似乎对边界指数的含义感到困惑。 考虑函数mergesort()的初始调用：

  mergesort(array,0,length,length,SortById); 

您为参数high和number_of_points传递相同的值，这很好，但它暗示high表示排序范围索引的独占上限。 但是， mergesort()实现似乎适用于参数high来表示包含边界。

你的merge()函数继续混淆，这可能是这里的主要罪魁祸首。 通过将传递的中点值作为右子arrays的起始索引，似乎期望中点作为左子arrays的排他上限，但当前的mergesort()实现传递包含上限。 另一方面， merge()执行的某些索引比较仅在middle是子数组的包含上限时才适用。

简而言之，你有一个混乱。 算法的基本概要看起来很好，但您需要决定（并自行记录）您的函数参数所代表的内容，并将您的实现细节与之协调。 如果我是你，我将对所有间隔采用半开式表示，以便下限始终包含，并且上限始终是独占的。 除此之外，其优点在于，每个中点值可以被正确地解释为其子arrays的左半部分的（独占）上限或者右半部分的（包含）下限。

Answer 2

  void mergesort(Points* set,int low,int high,int number_of_points, SortType sort) { int mid1; if((high-low)>1) { mid1 = (low+high)/2; mergesort(set, low, mid1, number_of_points, sort); mergesort(set, mid1, high, number_of_points, sort); merge(set, low, mid1, high, number_of_points, sort); } } void merge(Points* set, int low, int middle, int high, int number_of_points, SortType sort) { int leftIndex=low; int rightIndex=middle; int combinedIndex = low; Points tempArray[number_of_points]; int i; while(leftIndex <= middle && rightIndex < high) { if(set[leftIndex].id <= set[rightIndex].id) { tempArray[combinedIndex++] = set[leftIndex++]; } else tempArray[combinedIndex++] = set[rightIndex++]; } if(leftIndex == middle+1) { while(rightIndex < high) { tempArray[combinedIndex++] = set[rightIndex++]; } } else { while(leftIndex < middle) { tempArray[combinedIndex++] = set[leftIndex++]; } } for( i = low; i < high; i++) { set[i] = tempArray[i]; } } 0 18.000000 2.000000 1 13.000000 7.000000 10 19.000000 1.000000 0 18.000000 2.000000 12 16.000000 4.000000 13 14.000000 6.000000 29 5.000000 15.000000 31 2.000000 18.000000 32 6.000000 14.000000 32 1.000000 19.000000 39 0.000000 20.000000 39 0.000000 20.000000 52 12.000000 8.000000 31 2.000000 18.000000 68 3.000000 17.000000 77 9.000000 11.000000 78 10.000000 10.000000 12 16.000000 4.000000 79 15.000000 5.000000 85 8.000000 12.000000