linux线程池实现快速排序

下面是一个简单的基于Linux线程池的快速排序实现：

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

#define THREAD_MAX 8
#define MAX 1000

int array[MAX];
int count = 0;

pthread_mutex_t mutex;

typedef struct {
    int left;
    int right;
} task_t;

typedef struct {
    task_t *tasks;
    int count;
    int head;
    int tail;
    pthread_mutex_t mutex;
    pthread_cond_t cond;
} task_queue_t;

task_queue_t task_queue;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int *array, int left, int right) {
    int pivot = array[right];
    int i = left - 1;

    for (int j = left; j < right; j++) {
        if (array[j] < pivot) {
            i++;
            swap(&array[i], &array[j]);
        }
    }

    swap(&array[i + 1], &array[right]);

    return i + 1;
}

void quick_sort(int *array, int left, int right) {
    if (left < right) {
        int pivot_index = partition(array, left, right);
        quick_sort(array, left, pivot_index - 1);
        quick_sort(array, pivot_index + 1, right);
    }
}

void *worker_thread(void *arg) {
    task_t task;
    while (1) {
        pthread_mutex_lock(&task_queue.mutex);

        while (task_queue.count == 0) {
            pthread_cond_wait(&task_queue.cond, &task_queue.mutex);
        }

        task = task_queue.tasks[task_queue.head];
        task_queue.head = (task_queue.head + 1) % MAX;
        task_queue.count--;

        pthread_mutex_unlock(&task_queue.mutex);

        quick_sort(array, task.left, task.right);

        pthread_mutex_lock(&mutex);
        count++;
        pthread_mutex_unlock(&mutex);
    }

    return NULL;
}

void submit_task(task_t task) {
    pthread_mutex_lock(&task_queue.mutex);

    while (task_queue.count == MAX) {
        pthread_cond_wait(&task_queue.cond, &task_queue.mutex);
    }

    task_queue.tasks[task_queue.tail] = task;
    task_queue.tail = (task_queue.tail + 1) % MAX;
    task_queue.count++;

    pthread_cond_signal(&task_queue.cond);

    pthread_mutex_unlock(&task_queue.mutex);
}

int main() {
    pthread_t threads[THREAD_MAX];
    task_t task;

    pthread_mutex_init(&mutex, NULL);

    task_queue.tasks = malloc(sizeof(task_t) * MAX);
    task_queue.count = 0;
    task_queue.head = 0;
    task_queue.tail = 0;
    pthread_mutex_init(&task_queue.mutex, NULL);
    pthread_cond_init(&task_queue.cond, NULL);

    for (int i = 0; i < THREAD_MAX; i++) {
        pthread_create(&threads[i], NULL, worker_thread, NULL);
    }

    for (int i = 0; i < MAX; i += 100) {
        task.left = i;
        task.right = i + 99;
        submit_task(task);
    }

    while (count < MAX / 100) {
        // wait for all tasks to complete
    }

    for (int i = 0; i < MAX; i++) {
        printf("%d ", array[i]);
    }

    return 0;
}

该代码首先定义了一个 `task_t` 结构体，用于存储每个快速排序任务的左右边界。然后定义了一个任务队列 `task_queue_t`，用于存储所有待处理的任务。该队列包含一个 `tasks` 数组，用于存储所有任务，`count` 属性表示队列中当前的任务数，`head` 和 `tail` 属性表示队列头和尾的位置，`mutex` 和 `cond` 属性分别用于线程同步。定义了一个 `submit_task` 函数，用于将任务提交到任务队列中。

然后创建多个工作线程，每个工作线程不断从任务队列中获取任务，执行快速排序。每当一个任务完成时，使用互斥锁 `mutex` 统计完成的任务数。主线程循环等待所有任务完成，最后输出排序后的结果。

该代码中使用了互斥锁和条件变量来实现线程同步，保证任务队列的并发访问安全。同时使用了 Linux 系统的线程池来管理工作线程，避免了手动创建和销毁线程的复杂性。