面试题：C语言多线程快速排序实现

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/types.h>
#include <sys/sysinfo.h>

#define MAX_THREADS 64

// 定义结构体来传递参数给线程
typedef struct {
    int *arr;
    int low;
    int high;
} ThreadArgs;

// 交换两个整数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 划分函数，用于快速排序
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 线程执行的函数
void* threadedQuickSort(void* args) {
    ThreadArgs* threadArgs = (ThreadArgs*)args;
    quickSort(threadArgs->arr, threadArgs->low, threadArgs->high);
    pthread_exit(NULL);
}

// 合并函数，这里简单假设已经在各自线程中排序好，不需要额外合并操作
// 因为数组本身就是连续的，排序后直接就是整体有序
void merge(int arr[], int low, int mid, int high) {}

// 主函数
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int num_threads = get_nprocs();
    if (num_threads > MAX_THREADS) num_threads = MAX_THREADS;

    pthread_t threads[num_threads];
    ThreadArgs threadArgs[num_threads];
    int subArraySize = n / num_threads;

    for (int i = 0; i < num_threads; i++) {
        threadArgs[i].arr = arr;
        threadArgs[i].low = i * subArraySize;
        if (i == num_threads - 1) {
            threadArgs[i].high = n - 1;
        } else {
            threadArgs[i].high = (i + 1) * subArraySize - 1;
        }
        pthread_create(&threads[i], NULL, threadedQuickSort, &threadArgs[i]);
    }

    for (int i = 0; i < num_threads; i++) {
        pthread_join(threads[i], NULL);
    }

    // 简单示例中，这里没有复杂的合并操作
    // 实际应用中如果子数组不连续等情况，需要实现合并逻辑

    printf("排序后的数组: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

代码说明：
- 结构体定义：ThreadArgs结构体用于向线程传递数组指针、子数组的起始和结束索引。
- 交换函数：swap函数用于交换两个整数。
- 划分函数：partition函数是快速排序的核心划分函数，选择一个基准元素，将数组分为两部分。
- 快速排序函数：quickSort函数递归地对数组进行快速排序。
- 线程执行函数：threadedQuickSort函数是线程实际执行的函数，它调用quickSort对分配给该线程的子数组进行排序。
- 主函数：
  - 获取系统的CPU核心数，并根据核心数划分数组为多个子数组。
  - 创建线程，每个线程处理一个子数组的排序。
  - 等待所有线程完成，简单示例中没有复杂的合并操作，因为假设线程处理的子数组是连续的，排序后数组整体就有序了。实际应用中如果子数组不连续等情况，需要实现合并逻辑。最后输出排序后的数组。
线程同步：
- 使用pthread_join等待所有线程完成，确保所有子数组排序完成后再继续执行后续操作。
负载均衡：
- 根据CPU核心数划分数组为大致相等大小的子数组，尽量使每个线程处理的数据量相近，实现负载均衡。

星途面试题库

面试题：C语言多线程快速排序实现

知识考点

面试题答案