快排基本原理：
快速排序可以說(shuō)是最為常見(jiàn)的排序算法，冒泡排序時(shí)間復(fù)雜度達(dá)到了O（N2），而桶排序容易造成浪費(fèi)空間?？炫牛≦uicksort）就成為了不錯(cuò)的選擇。
1、原理：快排需要找一個(gè)數(shù)作為基準(zhǔn)數(shù)，用來(lái)參照。（可取第一個(gè)數(shù)為參照）
??????? 基準(zhǔn)數(shù)在中間某位置，兩端有指針，找到相應(yīng)數(shù)后，交換。
注意：若令第一個(gè)數(shù)為基準(zhǔn)數(shù)，先從右往左找，再?gòu)淖笸艺摇?/p>
2、優(yōu)點(diǎn)：平均時(shí)間復(fù)雜度O（NlogN)，相比冒泡排序每次交換可以是跳躍式的
排序過(guò)程：
代碼實(shí)現(xiàn)：
#include<mpi.h>
#include<time.h>
#include <stdlib.h>
#include <stdio.h>
int Partition(int* data, int start, int end) //劃分?jǐn)?shù)據(jù)
{
int temp = data[start]; //以第一個(gè)元素為基準(zhǔn)
while (start < end) {
while (start < end && data[end] >= temp)end--; //找到第一個(gè)比基準(zhǔn)小的數(shù)
data[start] = data[end];
while (start < end && data[start] <= temp)start++; //找到第一個(gè)比基準(zhǔn)大的數(shù)
data[end] = data[start];
}
data[start] = temp; //以基準(zhǔn)作為分界線
return start;
}
void QuickSort(int* data, int start, int end) //串行快排
{
if (start < end) { //未劃分完
int r = Partition(data, start, end); //繼續(xù)劃分，進(jìn)行遞歸排序
QuickSort(data, start, r - 1);
QuickSort(data, r + 1, end);
}
}
//求2的n次方
int exp2(int n)
{
int i = 1;
while (n-- > 0) i *= 2;
return i;
}
//求以2為底n的對(duì)數(shù)，向下取整
int log2(int n)
{
int i = 1, j = 2;
while (j < n) {
j *= 2;
i++;
}
return i;
}
void paraQuickSort(int* data, int start, int end, int m, int id, int nowID, int N)
{
int i, j, r = end, length = -1; //r表示劃分后數(shù)據(jù)前部分的末元素下標(biāo)，length表示后部分?jǐn)?shù)據(jù)的長(zhǎng)度
int* t;
MPI_Status status;
if (m == 0) { //無(wú)進(jìn)程可以調(diào)用
if (nowID == id) QuickSort(data, start, end);
return;
}
if (nowID == id) { //當(dāng)前進(jìn)程是負(fù)責(zé)分發(fā)的
while (id + exp2(m - 1) > N && m > 0) m--; //尋找未分配數(shù)據(jù)的可用進(jìn)程
if (id + exp2(m - 1) < N) { //還有未接收數(shù)據(jù)的進(jìn)程，則劃分?jǐn)?shù)據(jù)
r = Partition(data, start, end);
length = end - r;
MPI_Send(&length, 1, MPI_INT, id + exp2(m - 1), nowID, MPI_COMM_WORLD);
if (length > 0) //id進(jìn)程將后部分?jǐn)?shù)據(jù)發(fā)送給id+2^(m-1)進(jìn)程
MPI_Send(data + r + 1, length, MPI_INT, id + exp2(m - 1), nowID, MPI_COMM_WORLD);
}
}
if (nowID == id + exp2(m - 1)) { //當(dāng)前進(jìn)程是負(fù)責(zé)接收的
MPI_Recv(&length, 1, MPI_INT, id, id, MPI_COMM_WORLD, &status);
if (length > 0) { //id+2^(m-1)進(jìn)程從id進(jìn)程接收后部分?jǐn)?shù)據(jù)
t = (int*)malloc(length * sizeof(int));
if (t == 0) printf("Malloc memory error!");
MPI_Recv(t, length, MPI_INT, id, id, MPI_COMM_WORLD, &status);
}
}
j = r - 1 - start;
MPI_Bcast(&j, 1, MPI_INT, id, MPI_COMM_WORLD);
if (j > 0) //負(fù)責(zé)分發(fā)的進(jìn)程的數(shù)據(jù)不為空
paraQuickSort(data, start, r - 1, m - 1, id, nowID, N); //遞歸調(diào)用快排函數(shù)，對(duì)前部分?jǐn)?shù)據(jù)進(jìn)行排序
j = length;
MPI_Bcast(&j, 1, MPI_INT, id, MPI_COMM_WORLD);
if (j > 0) //負(fù)責(zé)接收的進(jìn)程的數(shù)據(jù)不為空
paraQuickSort(t, 0, length - 1, m - 1, id + exp2(m - 1), nowID, N); //遞歸調(diào)用快排函數(shù)，對(duì)前部分?jǐn)?shù)據(jù)進(jìn)行排序
if ((nowID == id + exp2(m - 1)) && (length > 0)) //id+2^(m-1)進(jìn)程發(fā)送結(jié)果給id進(jìn)程
MPI_Send(t, length, MPI_INT, id, id + exp2(m - 1), MPI_COMM_WORLD);
if ((nowID == id) && id + exp2(m - 1) < N && (length > 0)) //id進(jìn)程接收id+2^(m-1)進(jìn)程發(fā)送的結(jié)果
MPI_Recv(data + r + 1, length, MPI_INT, id + exp2(m - 1), id + exp2(m - 1), MPI_COMM_WORLD, &status);
}
int main(int argc, char* argv[])
{
int* data;
int rank, size;
int i, j, m, r, n = atoi(argv[1]); //隨機(jī)數(shù)組的長(zhǎng)度
double start_time, end_time;
MPI_Status status;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank); //當(dāng)前進(jìn)程的進(jìn)程號(hào)
MPI_Comm_size(MPI_COMM_WORLD, &size); //總進(jìn)程數(shù)
if (rank == 0) { //根進(jìn)程生成隨機(jī)數(shù)組
start_time = MPI_Wtime();
data = (int*)malloc(n * sizeof(int));
srand(time(NULL) + rand()); //隨機(jī)數(shù)種子
for (i = 0; i < n; i++)
data[i] = (int)rand(); //獲取n個(gè)隨機(jī)整數(shù)
}
m = log2(size); //第一次分發(fā)需要給第2^(m-1)個(gè)進(jìn)程
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD); //廣播n
paraQuickSort(data, 0, n - 1, m, 0, rank, size); //執(zhí)行快排
if (rank == 0) { //根進(jìn)程輸出并行時(shí)間
end_time = MPI_Wtime();
for (i = 0; i < 10 && i<n; i++)//輸出前十個(gè)元素
printf("%d ", data[i]);
printf("\n并行時(shí)間：%lfs\n", end_time - start_time);
}
MPI_Finalize();
}
運(yùn)行結(jié)果：
Mpi快排結(jié)果：
注1000后面的參數(shù)為生成隨機(jī)數(shù)的個(gè)數(shù)
編譯：mpicxx ./filename.cpp -o ./filename
Mpi基本原理：
??1.什么是MPI
Massage Passing Interface:是消息傳遞函數(shù)庫(kù)的標(biāo)準(zhǔn)規(guī)范，由MPI論壇開(kāi)發(fā)。
一種新的庫(kù)描述，不是一種語(yǔ)言。共有上百個(gè)函數(shù)調(diào)用接口，提供與C和Fortran語(yǔ)言的綁定
MPI是一種標(biāo)準(zhǔn)或規(guī)范的代表，而不是特指某一個(gè)對(duì)它的具體實(shí)現(xiàn)
MPI是一種消息傳遞編程模型，并成為這種編程模型的代表和事實(shí)上的標(biāo)準(zhǔn)
2.MPI的特點(diǎn)
MPI有以下的特點(diǎn)：
消息傳遞式并行程序設(shè)計(jì)
指用戶必須通過(guò)顯式地發(fā)送和接收消息來(lái)實(shí)現(xiàn)處理機(jī)間的數(shù)據(jù)交換。
在這種并行編程中，每個(gè)并行進(jìn)程均有自己獨(dú)立的地址空間，相互之間訪問(wèn)不能直接進(jìn)行，必須通過(guò)顯式的消息傳遞來(lái)實(shí)現(xiàn)。
這種編程方式是大規(guī)模并行處理機(jī)（MPP）和機(jī)群（Cluster）采用的主要編程方式。
并行計(jì)算粒度大，特別適合于大規(guī)模可擴(kuò)展并行算法
用戶決定問(wèn)題分解策略、進(jìn)程間的數(shù)據(jù)交換策略，在挖掘潛在并行性方面更主動(dòng),并行計(jì)算粒度大,特別適合于大規(guī)?？蓴U(kuò)展并行算法
消息傳遞是當(dāng)前并行計(jì)算領(lǐng)域的一個(gè)非常重要的并行程序設(shè)計(jì)方式
二、MPI的基本函數(shù)
MPI調(diào)用借口的總數(shù)雖然龐大，但根據(jù)實(shí)際編寫(xiě)MPI的經(jīng)驗(yàn)，常用的MPI函數(shù)是以下6個(gè)：
MPI_Init(…);
MPI_Comm_size(…);
MPI_Comm_rank(…);
MPI_Send(…);
MPI_Recv(…);
MPI_Finalize();
三、MPI的通信機(jī)制
MPI是一種基于消息傳遞的編程模型，不同進(jìn)程間通過(guò)消息交換數(shù)據(jù)。
1.MPI點(diǎn)對(duì)點(diǎn)通信類型
所謂點(diǎn)對(duì)點(diǎn)的通信就是一個(gè)進(jìn)程跟另一個(gè)進(jìn)程的通信，而下面的聚合通信就是一個(gè)進(jìn)程和多個(gè)進(jìn)程的通信。
- 標(biāo)準(zhǔn)模式：
該模式下MPI有可能先緩沖該消息，也可能直接發(fā)送，可理解為直接送信或通過(guò)郵局送信。是最常用的發(fā)送方式。
由MPI決定是否緩沖消息
沒(méi)有足夠的系統(tǒng)緩沖區(qū)時(shí)或出于性能的考慮，MPI可能進(jìn)行直接拷貝：僅當(dāng)相應(yīng)的接收完成后，發(fā)送語(yǔ)句才能返回。
這里的系統(tǒng)緩沖區(qū)是指由MPI系統(tǒng)管理的緩沖區(qū)。而非進(jìn)程管理的緩沖區(qū)。
MPI環(huán)境定義有三種緩沖區(qū)：應(yīng)用緩沖區(qū)、系統(tǒng)緩沖區(qū)、用戶向系統(tǒng)注冊(cè)的通信用緩沖區(qū)
MPI緩沖消息：發(fā)送語(yǔ)句在相應(yīng)的接收語(yǔ)句完成前返回。
這時(shí)后發(fā)送的結(jié)束或稱發(fā)送的完成== 消息已從發(fā)送方發(fā)出，而不是滯留在發(fā)送方的系統(tǒng)緩沖區(qū)中。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-497530.html
該模式發(fā)送操作的成功與否依賴于接收操作，我們稱之為非本地的，即發(fā)送操作的成功與否跟本地沒(méi)關(guān)系。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-497530.html
到了這里，關(guān)于使用mpi并行技術(shù)實(shí)現(xiàn)快排Qsort（）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
