我们得到一个未排序的整数数组。任务是使用通过多线程实现的合并排序技术对数组进行排序
合并排序
合并排序是一种基于分而治之技术的排序技术，我们将将数组分成相等的两半，然后以排序的方式将它们组合起来。
实现归并排序的算法是
检查是否有一个元素
-
否则，将数据递归地分成两半，直到无法再分为止。
立即学习“C++免费学习笔记（深入）”；
最后，按排序顺序将较小的列表合并为新列表。
多线程
在操作系统中，线程是负责执行部分任务的轻量级进程。线程共享公共资源来并发执行任务。
多线程是多任务处理的一种实现，我们可以在单个处理器上运行多个线程来并发执行任务。它将单个应用程序中的特定操作细分为单独的线程。每个线程都可以并行运行。
例如：
In −int arr[] = {3, 2, 1, 10, 8, 5, 7, 9, 4}
输出−排序后的数组为：1, 2, 3, 4, 5, 7, 8, 9, 10
解释-我们得到一个带有整数值的未排序数组。现在我们将使用多线程合并排序对数组进行排序。
In −int arr[] = {5, 3, 1, 45, 32, 21, 50} p>
输出−排序后的数组为：1, 3, 5, 21, 32, 45, 50
解释−我们给出具有整数值的未排序数组。现在我们将使用多线程合并排序对数组进行排序。
下面程序中使用的方法如下 -
我们将开始通过使用 C++ STL 中的 rand() 方法生成随机数。
创建 pthread_t 类型的数组，即 P_TH[thread_size]。
将函数作为组合数组调用(0、(大小 / 2 - 1) / 2、大小 / 2 - 1)、combine_array(大小 / 2、大小/2 + (大小-1-大小/2)/2、大小 - 1) 和 merge_array(0 , (size - 1)/2, size - 1)
打印存储在整数类型 arr[] 中的排序数组。
声明一个变量为set_val到temp_val++，首先要set_val * (size / 4 )，end 为 (set_val + 1) * (size / 4) - 1，mid_val 为first + (end - first) / 2
检查 IF first 小于 end then调用Sorting_Threading(first, mid_val)、Sorting_Threading(mid_val + 1, end)和combine_array(first, mid_val, end);
-
里面function void Sorting_Threading(int first, int end)
将变量声明为 mid_val to first + (end - first) / 2
检查 IF 首先小于 end，然后调用 Sorting_Threading(first, mid_val)、Sorting_Threading(mid_val + 1, end) 和 merge_array(first, mid_val, end)
-
函数内部 void merge_array(int first, int mid_val, int end)
-
将变量声明为 int* start 到new int[mid_val - first + 1]、int* last 到 new int[end - mid_val]、temp_1 到 mid_val - first + 1、temp_2 到 end - mid_val、i、j、k 到first。
li> 开始从 i 到 0 的 FOR 循环，直到 i 小于 temp_1。在循环内，将 start[i] 设置为 arr[i + first]。
开始从 i 到 0 的 FOR 循环，直到 i 小于 temp_2。在循环内部，将last[i]设置为arr[i + mid_val + 1]
将i设置为j为0。当i小于temp_1并且j小于时开始循环比 temp_2。在此期间，检查 IF start[i] 是否小于 last[j]，然后将 arr[k++] 设置为 start[i++]。否则，设置 arr[k++] = last[j++]
当 i 小于 temp_1 时开始，然后设置 arr[k++] = start[i++]。当 j 小于 temp_2 时开始，然后将 arr[k++] 设置为 last[j++]
-
开始从 i 到 0 的 FOR 循环，直到 i 小于线程的大小。在循环内部，调用 pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)NULL) 方法来创建具有给定数组值的线程。
函数内部void* Sorting_Threading(void* arg)
示例
#include#include #include #define size 20 #define thread_size 4 using namespace std; int arr[size]; int temp_val = 0; void combine_array(int first, int mid_val, int end){ int* start = new int[mid_val - first + 1]; int* last = new int[end - mid_val]; int temp_1 = mid_val - first + 1; int temp_2 = end - mid_val; int i, j; int k = first; for(i = 0; i < temp_1; i++){ start[i] = arr[i + first]; } for (i = 0; i < temp_2; i++){ last[i] = arr[i + mid_val + 1]; } i = j = 0; while(i < temp_1 && j < temp_2){ if(start[i] <= last[j]){ arr[k++] = start[i++]; } else{ arr[k++] = last[j++]; } } while (i < temp_1){ arr[k++] = start[i++]; } while (j < temp_2){ arr[k++] = last[j++]; } } void Sorting_Threading(int first, int end){ int mid_val = first + (end - first) / 2; if(first < end){ Sorting_Threading(first, mid_val); Sorting_Threading(mid_val + 1, end); combine_array(first, mid_val, end); } } void* Sorting_Threading(void* arg){ int set_val = temp_val++; int first = set_val * (size / 4); int end = (set_val + 1) * (size / 4) - 1; int mid_val = first + (end - first) / 2; if (first < end){ Sorting_Threading(first, mid_val); Sorting_Threading(mid_val + 1, end); combine_array(first, mid_val, end); } } int main(){ for(int i = 0; i < size; i++){ arr[i] = rand() % 100; } pthread_t P_TH[thread_size]; for(int i = 0; i < thread_size; i++){ pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)NULL); } for(int i = 0; i < 4; i++){ pthread_join(P_TH[i], NULL); } combine_array(0, (size / 2 - 1) / 2, size / 2 - 1); combine_array(size / 2, size/2 + (size-1-size/2)/2, size - 1); combine_array(0, (size - 1)/2, size - 1); cout<<"Merge Sort using Multi-threading: "; for (int i = 0; i < size; i++){ cout << arr[i] << " "; } return 0; }
输出
如果我们运行上面的代码，它将生成以下输出
Merge Sort using Multi-threading: 15 21 26 26 27 35 36 40 49 59 62 63 72 77 83 86 86 90 92 93
