c语言 - 当我用线程实现合并排序时得到不正确的输出，无法找出问题所在

Question

我已经处理这个问题大约3天了，我已经梳理了我的整个代码，试图找出为什么我得到了不正确的输出。这个程序的目的是使用线程进行合并排序。第一部分是简单地将元素并行排序为用户输入的多个段。测试的唯一输入将是2、5和10。要排序的数组将始终是由随机生成的数字组成的50 int数组。当输入的分段（由main顶部的变量"segments"表示）为2时，我的代码运行良好。然而，当我将分段更改为5或10时，我不会在末尾得到排序的数组。我尝试过使用print语句进行调试（我已经注释掉了，但您仍然可以看到），在前两次合并迭代中似乎出现了问题。由于某些原因，这些合并迭代的结果不符合顺序，并且它们包含重复的数字，这些数字在传递给它的原始数组中不存在重复。当我只将数组传递给它们时，我的排序方法和合并方法工作得很好，不使用线程，但当我使用线程时，我会得到无法解释的行为。下面是我的整个程序，要合并一个50的数组，它应该做以下操作：

• 将数组拆分为10个5的段，并对每个段进行排序
• 两人一组，一轮一轮地传球。因此，一轮应该在一段中通过0-5段，在另一段中穿过5-10段，10-15和15-20，20-25和25-30，以此类推，直到达到40-45和45-50
• 那么它将进入第二轮，第二轮的动作与第一轮相同。所以0-10和10-20，20-30和30-40，然后它不影响10的最后一部分
• 第三轮通过分段，以20:0-20和20-40成对合并，然后停止
• 最后，它应该将分段0-40与40-50合并

我的程序：（你应该主要关注我的主要功能，排序很好，合并看起来也很好，但我无论如何都包括了它们，以防万一）

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <pthread.h>
/**
 * Struct to contain an array partition as well as the size of the    partition.
 * Use struct to pass multiple parameters to pthread_create
 */
struct array_struct{
int *partition;
int size;
};
/**
 * Struct that contains two arrays (should be sorted) to merge
 * Use struct to pass multiple parameters to pthread_create
*/
struct arrays_to_merge{
int *array1;
int *array2;
int size1;
int size2;
};
//comparison function to use with qsort, sorts in ascending order
int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}

/**
 * Method that takes a struct containing a pointer to the first int in          an array 
 * partition, as well as the partition size. Object must be type void, used with pthread_create
 * @param pointer to the partition object. Type void
  */
void *sort(void *object){
struct array_struct *structure;
structure = (struct array_struct *) object;
int *array = structure->partition;
int size = structure->size;
int *i, j = 0;
qsort(array, size, sizeof(int), cmpfunc);
printf("Sorted %d elements.n", size);
}
void *merge(void * object){
struct arrays_to_merge *arrays_struct;
arrays_struct = (struct arrays_to_merge *) object;

int *array1 = arrays_struct->array1;
int *array2 = arrays_struct->array2;
int size1 = arrays_struct->size1;
int size2 = arrays_struct->size2;
int tempArray[size1 + size2];
int i = 0, j = 0, k = 0, duplicates = 0;
while (i < size1 && j < size2) {
    // printf("Merge number : %d  Comparing %d and %dn", mergenumber, array1[i], array2[j]);
    if (array1[i] <= array2[j]) {
        // printf("Picking %dn", array1[i]);
        tempArray[k] = array1[i];
        if (array1[i] == array2[j])
        {
            duplicates++;
        }
        i++;
        k++;
    }else {
         // printf("Merge number : %d Picking %dn", mergenumber, array2[j]);
        tempArray[k] = array2[j];
        k++; 
        j++;
    }
}
while (i < size1) {
    // printf("Merge number : %d   left over Picking %dn", mergenumber, array1[i]);
    tempArray[k] = array1[i];
    i++;
    k++;
}
while (j < size2) {
    // printf("Merge number : %d   left over Picking %dn", mergenumber, array2[j]);
    tempArray[k] = array2[j];
    k++;
    j++;
}
array1 = arrays_struct->array1;
for(i = 0; i < size1 + size2; i++){
    array1[i] = tempArray[i];
}
printf("Merged %d and %d elements with %d duplicatesn", size1, size2, duplicates);

}


//return an array of size 50 with randomly generated integers
int *randomArray(){
srand(time(NULL));
static int array[50];
int i;
for (i = 0; i < 50; ++i){
    array[i] = rand() % 51;
}
return array;
}

int main(int argc, char const *argv[])
{
int segments = 10;//make equal to argv input after testing
pthread_t threads[segments];

int i, *numbers; //iterator i, and pointer to int array 'numbers'
numbers = randomArray(); //return an array of random ints and store in 'numbers'
struct array_struct array[segments];
for(i = 0; i < segments; i++){
    int *partition = numbers + (i * (50/segments));//obtain the first index of partition
    array[i].partition = partition;
    array[i].size = 50/segments;
    pthread_create(&threads[i], NULL, sort, (void *) &array[i]);
}
for(i = 0; i < segments; i++){
    pthread_join(threads[i], NULL);
}

int count = segments;
struct arrays_to_merge arrays[segments];    
int j;
int size = 50/ segments;
while(count > 1){
    for(i = 0, j = 0; i < count-1; j++, i += 2){
        int *partition = numbers + (i * (size));
        int *partition2 = numbers + (i+1 * (size));
        arrays[j].array1 = partition;
        arrays[j].array2 = partition2;
        arrays[j].size1 = size;
        arrays[j].size2 = size;
        pthread_create(&threads[j], NULL, merge, (void *) &arrays[j]);
    }
    for(i = 0; i < j; i++){
        pthread_join(threads[i], NULL);
    }
    size = size * 2;
    count = count/2;
}
if(segments != 2){//for segments = 2, no need for his
    int *partition = numbers;
    int *partition2 = numbers + (size);
    arrays[0].array1 = partition;
    arrays[0].array2 = partition2;
    arrays[0].size1 = size;
    arrays[0].size2 = 50 - size;
    pthread_create(&threads[0], NULL, merge, (void *) &arrays[0]);
    pthread_join(threads[0], NULL); 
}   

for(i = 0; i < 50; i++){
    printf("%dn", numbers[i]);
}
pthread_exit(NULL);


return 0;
}

这是我的输出：

Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Merged 5 and 5 elements with 0 duplicates
Merged 5 and 5 elements with 0 duplicates
Merged 5 and 5 elements with 0 duplicates
Merged 5 and 5 elements with 0 duplicates
Merged 5 and 5 elements with 0 duplicates
Merged 10 and 10 elements with 3 duplicates
Merged 10 and 10 elements with 1 duplicates
Merged 20 and 20 elements with 7 duplicates
Merged 40 and 10 elements with 17 duplicates
0
6
9
11
12
13
13
14
15
17
19
23
25
25
25
26
26
28
28
28
28
30
32
32
32
34
39
41
41
44
44
44
44
44
50
50
9
15
50
9
15
19
26
50
50
9
15
11
14
50

很抱歉有这么长的文字墙，我已经试着自己解决了这个问题，但在拔了无数根头发之后，我想不通了。请帮我弄清楚我做错了什么。我认为我的问题在于我连接线程的方式，或者我的合并函数，但由于我不能确定，我只是包含了整个东西。

Answer 1

花了一段时间，但最终我到达了那里：）

问题出在这条线上：

    int *partition2 = numbers + (i+1 * (size));

这相当于（由于运算符优先级）。

int *partition2 = numbers + (i + size);

这不是你想要的。

应该是：

    int *partition2 = numbers + ((i+1) * (size));

请注意附加的括号。否则，partition2索引计算错误。因此，将与数组的不同部分合并。