pthread 并行实现快速排序并计时c++

下面是一个使用pthread实现的快速排序并计时的C代码：

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

#define MAX_N 1000000
#define MAX_THREAD_NUM 8

int a[MAX_N];
int n, num_threads;

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

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

int partition(int left, int right) {
    int pivot = a[left];
    int i = left, j = right + 1;
    while (1) {
        do {
            i++;
        } while (a[i] < pivot && i <= right);
        do {
            j--;
        } while (a[j] > pivot);
        if (i >= j) break;
        swap(&a[i], &a[j]);
    }
    swap(&a[left], &a[j]);
    return j;
}

void quicksort(int left, int right) {
    if (left >= right) return;
    int pivot_index = partition(left, right);
    quicksort(left, pivot_index - 1);
    quicksort(pivot_index + 1, right);
}

void *quicksort_thread(void *arg) {
    Range *range = (Range *)arg;
    int left = range->left;
    int right = range->right;
    if (left >= right) return NULL;
    int pivot_index = partition(left, right);
    if (num_threads > 1) {
        pthread_t thread_left, thread_right;
        Range range_left = {left, pivot_index - 1};
        Range range_right = {pivot_index + 1, right};
        if (num_threads > 2) {
            num_threads--;
            pthread_create(&thread_left, NULL, quicksort_thread, &range_left);
            quicksort_thread(&range_right);
            pthread_join(thread_left, NULL);
            num_threads++;
        } else {
            pthread_create(&thread_left, NULL, quicksort_thread, &range_left);
            quicksort_thread(&range_right);
            pthread_join(thread_left, NULL);
        }
    } else {
        quicksort(left, pivot_index - 1);
        quicksort(pivot_index + 1, right);
    }
    return NULL;
}

int main() {
    struct timeval start, end;
    srand(time(NULL));
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    printf("Enter the number of threads: ");
    scanf("%d", &num_threads);
    for (int i = 0; i < n; i++) {
        a[i] = rand() % 1000000;
    }
    gettimeofday(&start, NULL);
    pthread_t thread;
    Range range = {0, n - 1};
    pthread_create(&thread, NULL, quicksort_thread, &range);
    pthread_join(thread, NULL);
    gettimeofday(&end, NULL);
    printf("Time elapsed: %ld microseconds.\n",
           (end.tv_sec - start.tv_sec) * 1000000 + end.tv_usec - start.tv_usec);
    return 0;
}

在这个代码中，我们定义了一个数据结构`Range`，用于表示快速排序的左右边界。`quicksort_thread`函数是快速排序的线程函数，接受一个指向`Range`结构体的指针作为参数。如果当前线程数`num_threads`大于1，则递归地创建两个线程来分别处理左右两个子区间；否则，直接在当前线程中进行快速排序。

在主函数中，我们首先生成随机数作为排序的输入，然后调用`quicksort_thread`函数在多线程环境下进行快速排序，并使用`gettimeofday`函数计时。

需要注意的是，在递归创建线程时，我们需要先将`num_threads`减一，避免创建过多线程。此外，在创建线程时，我们需要传递一个指向`Range`结构体的指针作为线程参数，并在线程结束后调用`pthread_join`函数等待线程结束，防止线程未结束就退出程序。

需要编译时需要添加`-pthread`参数。