如何在Linux C环境下创建多线程实现对数万个数据的归并排序

在Linux C环境下，我们可以使用pthread库来创建多线程实现归并排序算法。下面是一个简单的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

// 定义线程参数结构体
typedef struct {
    int* arr;   // 待排序数组
    int start;  // 子数组的起始位置
    int end;    // 子数组的结束位置
} ThreadArgs;

// 归并排序函数
void merge(int arr[], int start, int mid, int end) {
    int n1 = mid - start + 1;
    int n2 = end - mid;

    int *left = (int*)malloc(n1 * sizeof(int));
    int *right = (int*)malloc(n2 * sizeof(int));

    for (int i = 0; i < n1; i++)
        left[i] = arr[start + i];
    for (int j = 0; j < n2; j++)
        right[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = start;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            arr[k] = left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = left[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = right[j];
        j++;
        k++;
    }

    free(left);
    free(right);
}

// 归并排序的递归函数
void mergeSort(int arr[], int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;

        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);

        merge(arr, start, mid, end);
    }
}

// 线程执行的函数
void* mergeSortThread(void* arg) {
    ThreadArgs* args = (ThreadArgs*)arg;

    mergeSort(args->arr, args->start, args->end);

    pthread_exit(NULL);
}

// 主函数
int main() {
    int n = 100000;  // 数据个数
    int* arr = (int*)malloc(n * sizeof(int));

    // 初始化待排序数组
    for (int i = 0; i < n; i++)
        arr[i] = rand() % 1000;

    int num_threads = 4;  // 线程数
    pthread_t* threads = (pthread_t*)malloc(num_threads * sizeof(pthread_t));
    ThreadArgs* thread_args = (ThreadArgs*)malloc(num_threads * sizeof(ThreadArgs));

    // 创建线程并分配任务
    int chunk_size = n / num_threads;
    for (int i = 0; i < num_threads; i++) {
        thread_args[i].arr = arr;
        thread_args[i].start = i * chunk_size;
        thread_args[i].end = (i == num_threads - 1) ? n - 1 : (i + 1) * chunk_size - 1;

        pthread_create(&threads[i], NULL, mergeSortThread, (void*)&thread_args[i]);
    }

    // 等待所有线程完成
    for (int i = 0; i < num_threads; i++)
        pthread_join(threads[i], NULL);

    // 合并每个子数组
    int step = chunk_size;
    while (step < n) {
        for (int start = 0; start < n; start += 2 * step) {
            int mid = start + step - 1;
            int end = (start + 2 * step - 1 < n) ? start + 2 * step - 1 : n - 1;
            merge(arr, start, mid, end);
        }
        step *= 2;
    }

    // 打印排序结果
    printf("Sorted array:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    // 释放内存
    free(arr);
    free(threads);
    free(thread_args);

    return 0;
}

在该示例代码中，我们使用了pthread库来创建多线程。首先，我们定义了一个线程参数结构体ThreadArgs，用于传递给线程函数mergeSortThread。merge函数用于合并两个有序数组，mergeSort函数用于递归地对子数组进行归并排序。

在主函数中，我们首先创建了一个包含随机整数的待排序数组arr。然后，我们创建了指定数量的线程，并为每个线程分配任务。每个线程处理一个子数组的归并排序。最后，我们使用merge函数合并每个子数组，并打印排序结果。

需要注意的是，在实际应用中，应根据机器的硬件和任务的复杂性来选择合适的线程数，以达到最佳性能。