利用pthread线程池实现快速排序并计时 c++

下面是一个利用 pthread 线程池实现快速排序并计时的 C 代码示例：

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/time.h>

#define MAX_SIZE 1000000
#define MAX_THREADS 4

// 定义线程池结构体
typedef struct {
    int* arr;
    int start;
    int end;
} ThreadArg;

pthread_t threads[MAX_THREADS];  // 线程池
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;  // 互斥锁

// 获取当前时间戳
double get_time() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec + tv.tv_usec * 1e-6;
}

// 交换数组中两个元素的值
void swap(int* arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 快速排序的递归函数
void quick_sort(int* arr, int start, int end) {
    if (start >= end) {
        return;
    }
    int pivot = arr[start];
    int i = start + 1, j = end;
    while (i <= j) {
        while (i <= end && arr[i] < pivot) {
            i++;
        }
        while (j > start && arr[j] >= pivot) {
            j--;
        }
        if (i < j) {
            swap(arr, i, j);
        }
    }
    swap(arr, start, j);
    quick_sort(arr, start, j - 1);
    quick_sort(arr, j + 1, end);
}

// 线程函数，对指定区间进行快速排序
void* thread_func(void* arg) {
    ThreadArg* thread_arg = (ThreadArg*) arg;
    quick_sort(thread_arg->arr, thread_arg->start, thread_arg->end);
    return NULL;
}

// 利用线程池进行快速排序
void parallel_quick_sort(int* arr, int size, int num_threads) {
    int step = size / num_threads;
    ThreadArg args[MAX_THREADS];
    for (int i = 0; i < num_threads; i++) {
        args[i].arr = arr;
        args[i].start = i * step;
        args[i].end = (i == num_threads - 1) ? size - 1 : (i + 1) * step - 1;
        pthread_create(&threads[i], NULL, thread_func, (void*) &args[i]);
    }
    for (int i = 0; i < num_threads; i++) {
        pthread_join(threads[i], NULL);
    }
    int pivot = arr[step - 1];
    int i = 0, j = size - 1;
    while (i <= j) {
        while (i <= size - 1 && arr[i] < pivot) {
            i++;
        }
        while (j >= step && arr[j] >= pivot) {
            j--;
        }
        if (i < j) {
            swap(arr, i, j);
        }
    }
    swap(arr, step - 1, j);
    if (num_threads > 1) {
        parallel_quick_sort(arr, j, num_threads / 2);
        parallel_quick_sort(arr + j + 1, size - j - 1, num_threads - num_threads / 2);
    } else {
        quick_sort(arr, 0, size - 1);
    }
}

int main() {
    int arr[MAX_SIZE];
    for (int i = 0; i < MAX_SIZE; i++) {
        arr[i] = rand() % MAX_SIZE;
    }
    double start_time = get_time();
    parallel_quick_sort(arr, MAX_SIZE, MAX_THREADS);
    double end_time = get_time();
    printf("Time used: %.6f seconds\n", end_time - start_time);
    return 0;
}

该代码利用线程池实现了并行的快速排序，其中线程池中的每个线程负责处理数组的一个区间。在主函数中，我们生成了一个随机数组，并用并行的方式对其进行排序，并输出排序所用的时间。注意到这里采用了一种递归方式，将数组分成两个部分进行排序，直至数组大小小于线程数时使用串行快速排序进行处理。