// 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）