C语言并行排序实战指南（从零开始掌握多线程高性能排序算法）

为什么选择快速排序进行并行化？

快速排序是一种分治算法，天然适合并行处理：每次划分后，左右子数组可以独立排序。这使得它成为实现多线程排序的理想选择。

准备工作

我们需要使用 POSIX 线程（pthreads）库来创建和管理线程。确保你的编译环境支持 pthread（Linux/macOS 默认支持，Windows 可使用 MinGW 或 WSL）。

完整代码实现

下面是一个完整的 C 语言并行快速排序实现：

#include <stdio.h>#include <stdlib.h>#include <pthread.h>#include <time.h>#define MAX_THREADS 4// 全局变量：控制最大线程数int thread_count = 0;pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;// 分区函数（标准快排分区）int partition(int arr[], int low, int high) {    int pivot = arr[high];    int i = (low - 1);    for (int j = low; j <= high - 1; j++) {        if (arr[j] < pivot) {            i++;            int temp = arr[i];            arr[i] = arr[j];            arr[j] = temp;        }    }    int temp = arr[i + 1];    arr[i + 1] = arr[high];    arr[high] = temp;    return (i + 1);}// 快速排序结构体（用于传递参数给线程）typedef struct {    int *arr;    int low;    int high;} SortArgs;// 线程执行函数void* quicksort_thread(void* args) {    SortArgs *s = (SortArgs*)args;    int low = s->low;    int high = s->high;    int *arr = s->arr;    if (low < high) {        int pi = partition(arr, low, high);        // 获取当前线程数        int current_threads;        pthread_mutex_lock(&mutex);        current_threads = thread_count;        pthread_mutex_unlock(&mutex);        // 如果线程数未达上限，创建新线程处理左半部分        if (current_threads < MAX_THREADS) {            pthread_mutex_lock(&mutex);            thread_count++;            pthread_mutex_unlock(&mutex);            SortArgs *left_args = malloc(sizeof(SortArgs));            left_args->arr = arr;            left_args->low = low;            left_args->high = pi - 1;            pthread_t left_thread;            pthread_create(&left_thread, NULL, quicksort_thread, left_args);            quicksort_thread(&(SortArgs){arr, pi + 1, high});            pthread_join(left_thread, NULL);            free(left_args);            pthread_mutex_lock(&mutex);            thread_count--;            pthread_mutex_unlock(&mutex);        } else {            // 否则顺序执行            quicksort_thread(&(SortArgs){arr, low, pi - 1});            quicksort_thread(&(SortArgs){arr, pi + 1, high});        }    }    return NULL;}// 主排序接口void parallel_quicksort(int arr[], int n) {    SortArgs args = {arr, 0, n - 1};    quicksort_thread(&args);}// 测试函数int main() {    const int SIZE = 10000;    int *arr = malloc(SIZE * sizeof(int));    // 随机生成数据    srand(time(NULL));    for (int i = 0; i < SIZE; i++) {        arr[i] = rand() % 10000;    }    printf("开始并行排序...\n");    clock_t start = clock();    parallel_quicksort(arr, SIZE);    clock_t end = clock();    double time_spent = ((double)(end - start)) / CLOCKS_PER_SEC;    printf("排序完成！耗时: %.4f 秒\n", time_spent);    // 验证是否排序成功（检查前10个元素）    printf("前10个元素: ");    for (int i = 0; i < 10; i++) {        printf("%d ", arr[i]);    }    printf("\n");    free(arr);    return 0;}

代码详解

• 分区函数：与传统快排相同，选取最后一个元素为基准，将数组分为小于和大于基准的两部分。
• 线程安全控制：使用互斥锁（mutex）保护全局线程计数器，防止多线程同时修改导致竞争条件。
• 动态线程创建：只有当当前活跃线程数小于设定上限（MAX_THREADS）时，才创建新线程；否则回退到顺序递归，避免线程爆炸。
• 参数传递：通过结构体 SortArgs 将数组指针和索引范围传递给线程函数。

编译与运行

在终端中执行以下命令编译程序（注意链接 pthread 库）：

gcc -o parallel_sort parallel_sort.c -lpthread -O2

然后运行：

./parallel_sort

性能提示

- 线程数并非越多越好，通常设置为 CPU 核心数或略高即可。
- 对于小数组（如 < 1000 元素），并行开销可能超过收益，建议设置阈值回退到普通快排。
- 使用 -O2 编译优化可显著提升性能。

总结

通过本教程，你已经掌握了如何用 C 语言实现一个高效的多线程排序系统。这种C语言并行排序技术不仅适用于快速排序，也可扩展到归并排序等其他分治算法。在实际项目中合理运用高性能排序算法，能让你的程序在处理海量数据时游刃有余！

记住：并行不是银弹，但用对了地方，它就是火箭推进器！