在C++中并行化歸并排序可以使用多線程來實現。一種常見的方法是使用C++標準庫中的std::thread
來創建多個線程來并行執行歸并排序算法。具體步驟如下:
將待排序的數組分成多個子數組,每個子數組分配給一個線程來排序。
在每個線程中使用歸并排序算法來對子數組進行排序。
將已排序的子數組合并成一個完整的有序數組。
下面是一個示例代碼:
#include <iostream>
#include <vector>
#include <thread>
void merge(std::vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
std::vector<int> L(n1), R(n2);
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
int 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++;
}
}
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
std::thread t1(mergeSort, std::ref(arr), left, mid);
std::thread t2(mergeSort, std::ref(arr), mid + 1, right);
t1.join();
t2.join();
merge(arr, left, mid, right);
}
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
int n = arr.size();
mergeSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
在上面的代碼中,我們使用了std::thread
來創建兩個線程來并行執行歸并排序算法。在mergeSort
函數中,我們首先創建兩個線程分別排序左半部分和右半部分的子數組,然后等待這兩個線程完成后再進行合并操作。通過這種方式,我們實現了并行化的歸并排序算法。