OpenMP编程实现并行快速排序算法

下面是使用OpenMP编写的并行快速排序算法的示例代码：

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

#define SIZE 1000000

void quicksort(int *arr, int left, int right);
int partition(int *arr, int left, int right);

int main() {
    int arr[SIZE];
    int i;

    // 初始化数组
    for (i = 0; i < SIZE; i++) {
        arr[i] = rand() % 100;
    }

    double start_time = omp_get_wtime();

    // 并行快速排序
    #pragma omp parallel
    {
        #pragma omp single nowait
        quicksort(arr, 0, SIZE-1);
    }

    double end_time = omp_get_wtime();

    // 验证排序结果
    for (i = 0; i < SIZE-1; i++) {
        if (arr[i] > arr[i+1]) {
            printf("Sort Error!\n");
            break;
        }
    }

    printf("Sort Done!\n");
    printf("Time: %f seconds\n", end_time-start_time);

    return 0;
}

void quicksort(int *arr, int left, int right) {
    int pivot;

    if (left < right) {
        pivot = partition(arr, left, right);

        #pragma omp task shared(arr)
        {
            quicksort(arr, left, pivot-1);
        }

        #pragma omp task shared(arr)
        {
            quicksort(arr, pivot+1, right);
        }
    }
}

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

    for (j = left; j <= right-1; j++) {
        if (arr[j] <= pivot) {
            i++;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    temp = arr[i+1];
    arr[i+1] = arr[right];
    arr[right] = temp;

    return i+1;
}

在这个例子中，我们使用了OpenMP的任务并行来实现快速排序。在`quicksort`函数中，我们使用了`#pragma omp task`指令来创建任务，并使用`shared`属性来共享数组`arr`。这里的`nowait`属性告诉OpenMP不要等待任务完成，而是继续执行下一个语句。

在`main`函数中，我们使用了`#pragma omp parallel`指令来创建线程，并使用`single`属性来保证`quicksort`函数只被调用一次。`omp_get_wtime`函数用于计时。

最后，我们验证了排序结果，并输出了执行时间。

需要注意的是，为了避免任务创建过多导致性能下降，我们可以使用`if`子句来控制任务的创建。例如，在`quicksort`函数中，当`left < right`时才创建任务，否则直接进行串行排序。