基于 OpenMP 的快速排序算法代码1调用 omp_set_num_threads 函数设置线程数numThreads利用 parallel 指令将代码复制到 no 个线程上执行。2将排序任务划分到不同的线程中去每个子线程调用 omp_get_num_threads 函数获取当前线程号。主线程调用 omp_get_num_threads 函数获取当前并行的线程个数barrier指令设置栅栏mas

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

void quicksort(int *arr, int left, int right) { if (left >= right) { return; }

int i = left;
int j = right;
int key = arr[left];

while (i < j) {
    while (i < j && arr[j] >= key) {
        j--;
    }
    arr[i] = arr[j];
    
    while (i < j && arr[i] <= key) {
        i++;
    }
    arr[j] = arr[i];
}

arr[i] = key;

// Recursively sort the two halves
quicksort(arr, left, i - 1);
quicksort(arr, i + 1, right);

}

void merge(int *arr, int left, int middle, int right) { int i, j, k; int n1 = middle - left + 1; int n2 = right - middle;

int *L = (int*)malloc(n1 * sizeof(int));
int *R = (int*)malloc(n2 * sizeof(int));

for (i = 0; i < n1; i++) {
    L[i] = arr[left + i];
}
for (j = 0; j < n2; j++) {
    R[j] = arr[middle + 1 + j];
}

i = 0;
j = 0;
k = left;

while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
        arr[k] = L[i];
        i++;
    } else {
        arr[k] = R[j];
        j++;
    }
    k++;
}

while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
}

while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
}

free(L);
free(R);

}

void parallel_merge_sort(int *arr, int size) { int numThreads = omp_get_max_threads();

#pragma omp parallel num_threads(numThreads)
{
    int threadNum = omp_get_thread_num();
    int start = threadNum * (size / numThreads);
    int end = (threadNum + 1) * (size / numThreads) - 1;
    
    if (threadNum == numThreads - 1) {
        end = size - 1;
    }
    
    quicksort(arr, start, end);
    
    #pragma omp barrier
    
    for (int mergeSize = 2; mergeSize <= numThreads; mergeSize *= 2) {
        int mergeOffset = mergeSize / 2;
        
        if (threadNum % mergeSize == 0 && threadNum + mergeOffset < numThreads) {
            int mergeStart = threadNum * (size / numThreads);
            int mergeMiddle = mergeStart + mergeOffset * (size / numThreads) - 1;
            int mergeEnd = (threadNum + mergeSize) * (size / numThreads) - 1;
            
            if (threadNum + mergeSize == numThreads) {
                mergeEnd = size - 1;
            }
            
            merge(arr, mergeStart, mergeMiddle, mergeEnd);
        }
        
        #pragma omp barrier
    }
}

}

int main() { int arr[] = {9, 3, 7, 5, 2, 1, 8, 4, 6}; int size = sizeof(arr) / sizeof(arr[0]);

parallel_merge_sort(arr, size);

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

return 0;