// EnumSort.cpp : 定义控制台应用程序的入口点。
//枚举排序
/*
枚举排序(Enumeration Sort)是一种最简单的排序算法,通常也称为秩排序(Rank Sort)。
该算法的具体思想是(假设按关键字递增排序),对每一个待排序的元素统计小于它的所有元素的个数,从而得到该元素最终处于序列中的位置。
假定待排序的n个数存在a[1]…a[n]中。首先将a[1]与a[2]…a[n]比较,记录比其小的数的个数,令其为k,
a[1]就被存入有序的数组b[1]…b[n]的b[k+1]位置上;然后将a[2]与a[1],a[3]…a[n]比较,记录比其小的数的个数,依此类推。
这样的比较操作共n(n-1)次,所以串行秩排序的时间复杂度为O(n2)。
*/
#include "stdafx.h"
#include <Windows.h>
#include <omp.h>
#include <time.h>
#include <iostream>
using namespace std; #define NUM_THREADS 2
#define maxN 100000
int _tmain(int argc, _TCHAR* argv[])
{
int i,j,k;
clock_t t1,t2;
omp_set_num_threads(NUM_THREADS);
int a[maxN];//={0,4,9,6,1,5,3,8,7,2};
int b[maxN];
//并行——————————;
for (i=0;i<maxN;i++)
{
a[i]=maxN-i;
}
t1=clock();
#pragma omp parallel sections private(i,j,k)
{
/*#pragma omp for
for (i=0;i<maxN;i++)
{
k=0;
for (j=0;j<maxN;j++)
{
if (a[i]>a[j])
{
k++;
}
}
b[k]=a[i];
}*/
#pragma omp section
{
for (i=omp_get_thread_num();i<maxN;i=i+NUM_THREADS)
{
k=0;
for (j=0;j<maxN;j++)
{
if (a[i]>a[j])//找出数组中比自己小的元素的个数k;
{
k++;
}
}
b[k]=a[i];//另外建立一个数组,将其放到第k+1处;
}
}
#pragma omp section
{
for (i=omp_get_thread_num();i<maxN;i=i+NUM_THREADS)
{
k=0;
for (j=0;j<maxN;j++)
{
if (a[i]>a[j])
{
k++;
}
}
b[k]=a[i];
}
}
}
t2=clock();
cout<<"并行时间:"<<t2-t1<<endl;
for (i=99900;i<maxN;i++)
{
cout<<b[i]<<" ";
}
cout<<endl; //串行————————————;
for (i=0;i<maxN;i++)
{
a[i]=maxN-i;
}
t1=clock();
for (i=0;i<maxN;i++)
{
k=0;
for (j=0;j<maxN;j++)
{
if (a[i]>a[j])
{
k++;
}
}
b[k]=a[i];
}
t2=clock();
cout<<"串行时间:"<<t2-t1<<endl;
for (i=99900;i<maxN;i++)
{
cout<<b[i]<<" ";
}
cout<<endl;
system("pause");
return 0;
}

运行结果如下图:(相对加速比:1.72)

OpenMP之枚举排序-LMLPHP

05-07 10:23