資料結構
網路
關係資料庫管理系統 (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+ 次瀏覽
