数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++多线程实现归并排序
给定一个未排序的整数数组，任务是使用多线程实现的归并排序技术对该数组进行排序。
归并排序
归并排序是一种基于分治法的排序技术，我们将数组分成相等的两半，然后以排序的方式合并它们。
实现归并排序的算法是：
检查列表中是否只有一个元素，如果是，则返回该元素。
否则，递归地将数据分成两半，直到无法再进一步划分。
最后，将较小的列表按排序顺序合并到新的列表中。
多线程
在操作系统中，**线程**是负责执行任务一部分的轻量级进程。线程共享公共资源以并发执行任务。
**多线程**是一种多任务实现，我们可以在单个处理器上运行多个线程以并发执行任务。它将单个应用程序中的特定操作细分为各个线程。每个线程都可以并行运行。
例如：
输入−int arr[] = {3, 2, 1, 10, 8, 5, 7, 9, 4}
输出−排序后的数组是：1, 2, 3, 4, 5, 7, 8, 9, 10
说明−我们得到一个包含整数值的未排序数组。现在，我们将使用多线程归并排序对数组进行排序。
输入−int arr[] = {5, 3, 1, 45, 32, 21, 50}
输出−排序后的数组是：1, 3, 5, 21, 32, 45, 50
说明−我们得到一个包含整数值的未排序数组。现在，我们将使用多线程归并排序对数组进行排序。
下面程序中使用的方法如下：
我们将首先使用 C++ STL 中的 rand() 方法生成随机数。
创建一个 pthread_t 类型的数组，即 P_TH[thread_size]。
从 i=0 开始循环，直到 i 小于线程大小。在循环内，调用 pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)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)
打印存储在整数类型 arr[] 中的排序数组。
在函数 void* Sorting_Threading(void* arg) 内
声明一个变量 set_val 为 temp_val++，first 为 set_val * (size / 4)，end 为 (set_val + 1) * (size / 4) - 1，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(int first, int end) 内
声明变量 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 combine_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。
从 i=0 开始循环，直到 i 小于 temp_1。在循环内，将 start[i] 设置为 arr[i + first]。
从 i=0 开始循环，直到 i 小于 temp_2。在循环内，将 last[i] 设置为 arr[i + mid_val + 1]
将 i 和 j 设置为 0。开始 While 循环，直到 i 小于 temp_1 且 j 小于 temp_2。在 while 循环内，检查 IF start[i] 小于 last[j]，然后将 arr[k++] 设置为 start[i++]。否则，将 arr[k++] 设置为 last[j++]
开始 While 循环，直到 i 小于 temp_1，然后将 arr[k++] 设置为 start[i++]。开始 While 循环，直到 j 小于 temp_2，然后将 arr[k++] 设置为 last[j++]
示例
#include <iostream>
#include <pthread.h>
#include <time.h>
#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
4K+ 次浏览
