정렬 알고리즘 및 병렬 분석

#include "stdlib.h"
#include "iostream"
#include "omp.h"
#include "time.h"
#include "vector"
#include "stack"
using namespace std;

//#define random(x) (rand()%x)
#define BOUNDARY 1000000000	//          
#define MAX_NUM 1000000	//         
const double MinProb = 1.0 / (RAND_MAX + 1);	//  
typedef int KeyInt;
//            [low,high]  
typedef struct Region
{
	int low;
	int high;
}Region;

：

KeyInt* randomCreate(int N);
bool happened(double probability);
int myrandom(int n);//  0~n-1         
void DisPlay(int N, KeyInt *p);
KeyInt* BubbleAlgorithm(int N, KeyInt *p);//    
KeyInt* BubbleAlgorithmParallel(int N, KeyInt *p);//    
KeyInt* InsertSort(int N, KeyInt *p);//    
KeyInt* InsertSort(int *p, int low, int high);//        
vector InsertSortPart(int N, KeyInt *p);//       
vector InsertSortParallel(int N, KeyInt *p);//      
vector InsertVector(vector &vec, int value);
vector InsertVectorSort(vector &vec); 
KeyInt* ShellSort(int N, KeyInt *p);//    
KeyInt* ShellSortParallel(int N, KeyInt *p);//      
KeyInt* InsertSort(int N, KeyInt *p, int start, int inc);//              
void MergeSort(KeyInt *p, KeyInt *temp, int l, int r);//    
void MergeSort(KeyInt *p, int N);//       
void MergeSortParallel(KeyInt *p, KeyInt *temp, int l, int r);//2     
void MergeSortParallel(KeyInt *p, KeyInt *temp, int N);//4     
void MergeSortParallel(KeyInt *p, int N);//         
void Merge(KeyInt *p, KeyInt *temp, int l, int r);//  
void QuickSort(KeyInt *p, int low, int high);//  
void QuickSortAverage(KeyInt *p, int low, int high);//  +    +  
void QuickSortSame(KeyInt *p, int low, int high);//  +    +  +      
int SelectPivotMedianOfThree(int *arr, int low, int high);//    
int Partition(int * a, int low, int high);//  
void NonRecursiveQuickSort(int *a, int len);//      
void QuickSortParallel(KeyInt *p, int low, int high);//2   
void QuickSortParallel4Core(KeyInt *p, int low, int high);//4   

KeyInt* BubbleAlgorithm(int N, KeyInt *p)	//    
{
	int i, j;
	KeyInt temp;
//#pragma omp parallel for
	for (i = 0; ip[j+1])
			{
				temp = p[j];
				p[j] = p[j+1];
				p[j+1] = temp;
			}
	return (p);
}

， ， ， ， n-1 。 for n*(n-1)/2 ， o(n^2)。 ， ， ， 。 ， ， （Odd-even Sort）。

KeyInt* BubbleAlgorithmParallel(int N, KeyInt *p)	//    Odd-even Sort
{
	int i, j;
	for (i = 1; i < N; i++) {
		if ((i&0x1) == 1) {
#pragma omp parallel for
			for (j = 0; j < N - 1; j += 2) {
				if (p[j] > p[j + 1]) {
					int temp = p[j];
					p[j] = p[j + 1];
					p[j + 1] = temp;
				}
			}
		}
		else {
#pragma omp parallel for
			for (j = 2; j < N; j += 2) {
				if (p[j-1] > p[j]) {
					int temp = p[j-1];
					p[j-1] = p[j];
					p[j] = temp;
				}
			}
		}
	}
	return (p);
}

， ， 。 #pragma omp parallel for openmp ， for 。

， 。

odd-even sort 。 
， array array[i] item(array[i + 1]) ； 
， array array[i] item(array[i - 1]) ；

， ， ， 。 ， ， ， 。

KeyInt* InsertSort(int N, KeyInt *p)//    
{
	int temp;
	for (int i = 1; i < N; i++) {
		for (int j = i; (j > 0) && (p[j] < p[j - 1]); j--) {
			temp = p[j];
			p[j] = p[j - 1];
			p[j - 1] = temp;
		}
	}
	return p;
}

 
  n ， ： 　　
  {{a1}，{a2，a3，a4，…，an}} 　　
 {{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}} 　
 {{a1(n-1），a2(n-1) ，…},{an(n-1)}} 　　
  ，
  ， 。

KeyInt* InsertSort(int *p, int low, int high)//        ，    p           
{
	int temp;
	for (int i = low+1; i <= high; i++) {
		for (int j = i; (j > low) && (p[j] < p[j - 1]); j--) {
			temp = p[j];
			p[j] = p[j - 1];
			p[j - 1] = temp;
		}
	}
	return p;
}

vector InsertVector(vector &vec, int value) {	//vector      
	if (vec.size() == 0) {
		vec.push_back(value);
		return vec;
	}
	vec.push_back(value);
	//int temp;
	for (int j = vec.size()-1; j > 0; j--) {
		if (vec[j] < vec[j - 1]) {
			/*temp = vec[j];
			vec[j] = vec[j - 1];
			vec[j - 1] = temp;*/
			swap(vec[j-1], vec[j]);
		}
		else if (vec[j] >= vec[j - 1])
			break;
	}
	return vec;
}

vector InsertVectorSort(vector &vec)
{
	//int temp;
	for (int i = 1; i < vec.size(); i++) {
		for (int j = i; j > 0; j--) {
			if (vec[j] < vec[j - 1]) {
				/*temp = vec[j];
				vec[j] = vec[j - 1];
				vec[j - 1] = temp;*/
				swap(vec[j - 1], vec[j]);
			}
			else if (vec[j] >= vec[j - 1])
				break;
		}
	}
	return vec;
}

vector InsertSortPart(int N, KeyInt *p)//       
{
	int i;
	int interval = BOUNDARY / 4;
	vector vec[4];


	for (i = 0; i < N; i++) {
		if (p[i] < interval)
			vec[0].push_back(p[i]);
		else if (p[i] < 2 * interval)
			vec[1].push_back(p[i]);
		else if (p[i] < 3 * interval)
			vec[2].push_back(p[i]);
		else
			vec[3].push_back(p[i]);
	}
	int* arr0 = new int[vec[0].size()];
	int* arr1 = new int[vec[1].size()];
	int* arr2 = new int[vec[2].size()];
	int* arr3 = new int[vec[3].size()];
	for (i = 0; i < vec[0].size(); i++)
		arr0[i] = vec[0][i];
	for (i = 0; i < vec[1].size(); i++)
		arr1[i] = vec[1][i];
	for (i = 0; i < vec[2].size(); i++)
		arr2[i] = vec[2][i];
	for (i = 0; i < vec[3].size(); i++)
		arr3[i] = vec[3][i];

	arr0 = InsertSort(vec[0].size(), arr0);
	arr1 = InsertSort(vec[1].size(), arr1);
	arr2 = InsertSort(vec[2].size(), arr2);
	arr3 = InsertSort(vec[3].size(), arr3);

	vector vec1[4];
	for (i = 0; i < vec[0].size(); i++)
		vec1[0].push_back(arr0[i]);
	for (i = 0; i < vec[1].size(); i++)
		vec1[1].push_back(arr1[i]);
	for (i = 0; i < vec[2].size(); i++)
		vec1[2].push_back(arr2[i]);
	for (i = 0; i < vec[3].size(); i++)
		vec1[3].push_back(arr3[i]);
	vec1[0].insert(vec1[0].end(), vec1[1].begin(), vec1[1].end());
	vec1[0].insert(vec1[0].end(), vec1[2].begin(), vec1[2].end());
	vec1[0].insert(vec1[0].end(), vec1[3].begin(), vec1[3].end());

	return vec1[0];
}

vector InsertSortParallel(int N, KeyInt *p)//      
{
	int i;
	int interval = BOUNDARY / 4;
	vector vec[4];
	//vec[0].reserve(MAX_NUM);
	//vec[1].reserve(MAX_NUM/2);
	//vec[2].reserve(MAX_NUM/2);
	//vec[3].reserve(MAX_NUM/2);
	
	//long start = clock();
	for (i = 0; i < N; i++) {
		if (p[i] < interval)
			vec[0].push_back(p[i]);
		else if (p[i] < 2 * interval)
			vec[1].push_back(p[i]);
		else if (p[i] < 3 * interval)
			vec[2].push_back(p[i]);
		else
			vec[3].push_back(p[i]);
	}
	//long end = clock();
	//printf("The time1 is:%lf
", (double)(end - start));
	//printf("%d %d %d %d
", vec[0].size(), vec[1].size(), vec[2].size(), vec[3].size);
	//cout << vec[0].size() << '
';
	//cout << vec[1].size() << '
';
	//cout << vec[2].size() << '
';
	//cout << vec[3].size() << '
';
	//long start1 = clock();
	int* arr0 = new int[vec[0].size()];
	int* arr1 = new int[vec[1].size()];
	int* arr2 = new int[vec[2].size()];
	int* arr3 = new int[vec[3].size()];
	for (i = 0; i < vec[0].size(); i++)
		arr0[i] = vec[0][i];
	for (i = 0; i < vec[1].size(); i++)
		arr1[i] = vec[1][i];
	for (i = 0; i < vec[2].size(); i++)
		arr2[i] = vec[2][i];
	for (i = 0; i < vec[3].size(); i++)
		arr3[i] = vec[3][i];
	omp_set_num_threads(4);

#pragma omp parallel
	{
#pragma omp sections
	{
#pragma omp section
	{
		//InsertVectorSort(vec[0]);
		arr0 = InsertSort(vec[0].size(), arr0);
		//printf("%d
", omp_get_thread_num());
	}
#pragma omp section
	{
		//InsertVectorSort(vec[1]);
		arr1 = InsertSort(vec[1].size(), arr1);
		//printf("%d
", omp_get_thread_num());
	}
#pragma omp section
	{
		//InsertVectorSort(vec[2]);
		arr2 = InsertSort(vec[2].size(), arr2);
		//printf("%d
", omp_get_thread_num());
	}
#pragma omp section
	{
		//InsertVectorSort(vec[3]);
		arr3 = InsertSort(vec[3].size(), arr3);
		//printf("%d
", omp_get_thread_num());
	}
	}
	}
	
	/*InsertVectorSort(vec[0]);
	InsertVectorSort(vec[1]);
	InsertVectorSort(vec[2]);
	InsertVectorSort(vec[3]);*/
	/*arr0 = InsertSort(vec[0].size(), arr0);
	arr1 = InsertSort(vec[1].size(), arr1);
	arr2 = InsertSort(vec[2].size(), arr2);
	arr3 = InsertSort(vec[3].size(), arr3);*/
	//long end1 = clock();
	//printf("The time2 is:%lf
", (double)(end1 - start1));
	/*vec[0].clear();
	vec[1].clear();
	vec[2].clear();
	vec[3].clear();*/
	//long start2 = clock();
	vector vec1[4];
	for (i = 0; i < vec[0].size(); i++)
		vec1[0].push_back(arr0[i]);
	for (i = 0; i < vec[1].size(); i++)
		vec1[1].push_back(arr1[i]);
	for (i = 0; i < vec[2].size(); i++)
		vec1[2].push_back(arr2[i]);
	for (i = 0; i < vec[3].size(); i++)
		vec1[3].push_back(arr3[i]);
	vec1[0].insert(vec1[0].end(), vec1[1].begin(), vec1[1].end());
	vec1[0].insert(vec1[0].end(), vec1[2].begin(), vec1[2].end());
	vec1[0].insert(vec1[0].end(), vec1[3].begin(), vec1[3].end());
	//long end2 = clock();
	//printf("The time3 is:%lf
", (double)(end2 - start2));
	return vec1[0];
	/*vec[0].insert(vec[0].end(), vec[1].begin(), vec[1].end());
	vec[0].insert(vec[0].end(), vec[2].begin(), vec[2].end());
	vec[0].insert(vec[0].end(), vec[3].begin(), vec[3].end());
	return vec[0];*/
}

/*
 * ： n d1 ，
 * （n d1） 。 d1 。
 * ； ， d2  * dt=1(dt  */

KeyInt* ShellSort(int N, KeyInt *p)	//    
{
	for (int i = N / 2; i > 2; i /= 2) {
		for (int j = 0; j < i; j++) {
			InsertSort(N, p, j, i);
		}
	}
	InsertSort(N, p, 0, 1);
	return p;
}

KeyInt* ShellSortParallel(int N, KeyInt *p)//      
{
	for (int i = N / 2; i > 2; i /= 2) {
#pragma omp parallel for
		for (int j = 0; j < i; j++) {
			InsertSort(N, p, j, i);
		}
	}
	InsertSort(N, p, 0, 1);
	return p;
}

KeyInt* InsertSort(int N, KeyInt *p, int start, int inc)//              
{
	int temp;
	for (int i = start + inc; i < N; i += inc) {
		for (int j = i; (j >= inc) && (p[j] < p[j - inc]); j -= inc) {
			int temp = p[j];
			p[j] = p[j-inc];
			p[j-inc] = temp;
		}
	}
	return p;
}

/*
 * , 　　 
 * ： d1  * ； d2  * ：d=5 　　49 38 65 97 76 13 27 49 55 04 　　 
 * 49 13 　　|-------------------| 　　 
 * 38 27     |-------------------| 　　 
 * 65 49 　　|-------------------| 　　 
 * 97 55     |-------------------| 　　 
 * 76 04 　　|-------------------| 　　 
 * 　　13 27 49 55 04 49 38 65 97 76 　　 
 * d=3 　　 13 27 49  55 04 49 38 65 97 76 　　 
 * 13 55 38 76 |------------|------------|------------| 　　 
 * 27 04 65 |------------|------------| 　　 
 * 49 49 97 |------------|------------| 　　
 *  13 04 49* 38 27 49 55 65 97 76 　　 
 * d=1 　　13 04 49 38 27 49 55 65 97 76
 * 　　 |----|----|----|----|----|----|----|----|----| 　　 　　
 * 04 13 27 38 49 49 55 65 76 97
 */

void Merge(KeyInt *p, KeyInt *temp, int l, int r)//  
{
	int mid = (l + r) / 2;
	int i1 = l;
	int i2 = mid + 1;
	for (int cur = l; cur <= r; cur++) {
		if (i1 == mid + 1)
			p[cur] = temp[i2++];
		else if (i2 > r)
			p[cur] = temp[i1++];
		else if (temp[i1] < temp[i2])
			p[cur] = temp[i1++];
		else
			p[cur] = temp[i2++];
	}
}

void MergeSort(KeyInt *p, KeyInt *temp, int l, int r)	//    
{
	int mid = (l + r) / 2;
	if (l == r)
		return;
	
	MergeSort(p, temp, l, mid);
	MergeSort(p, temp, mid + 1, r);

	for (int i = l; i <= r; i++) {
		temp[i] = p[i];
	}
	/*int i1 = l;
	int i2 = mid + 1;
	for (int cur = l; cur <= r; cur++) {
		if (i1 == mid + 1)
			p[cur] = temp[i2++];
		else if (i2 > r)
			p[cur] = temp[i1++];
		else if (temp[i1] < temp[i2])
			p[cur] = temp[i1++];
		else
			p[cur] = temp[i2++];
	}*/
	Merge(p, temp, l, r);
}

void MergeSort(KeyInt *p, int N)//       
{
	int i, left_min, left_max, right_min, right_max, next;
	int *tmp = (int*)malloc(sizeof(int) * N);
	
	for (i = 1; i < N; i *= 2) // i   ，1,2,4,8……
	{
	    for (left_min = 0; left_min < N - i; left_min = right_max)
		 {
			right_min = left_max = left_min + i;
			right_max = left_max + i;

			if (right_max > N)
				right_max = N;

			next = 0;
			while (left_min < left_max && right_min < right_max)
					tmp[next++] = p[left_min] > p[right_min] ? p[right_min++] : p[left_min++];

			while (left_min < left_max)
				p[--right_min] = p[--left_max];

			while (next > 0)
				p[--right_min] = tmp[--next];
		 }
	}
	
	free(tmp);
}

/*
 * (merge)， ， 。 　　
 * {6，202，100，301，38，8，1} 　　
 * ： [6] [202] [100] [301] [38] [8] [1] 　　
 * i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ]　3 　　
 * i=2 [ 6 100 202 301 ] [ 1 8 38 ]　4 　　
 * i=3　[ 1 6 8 38 100 202 301 ] 4 
 */

void MergeSortParallel(KeyInt *p, int N)//         
{
	//int left_max, right_min, right_max, next;
	int *tmp = (int*)malloc(sizeof(int) * N);
	for (int i = 1; i < N; i *= 2) // i   ，1,2,4,8……
	{
#pragma omp parallel for
		for (int left_min = 0; left_min < N - i; left_min += 2*i)
		{
			//int *tmp = (int*)malloc(sizeof(int) * 2*i);
			int temp = left_min;
			int right_min = temp + i;
			int left_max = temp + i;
			int right_max = left_max + i;


			if (right_max > N)
				right_max = N;

			//int next = 0;
			int next = left_min;
			while (temp < left_max && right_min < right_max)
				tmp[next++] = p[temp] > p[right_min] ? p[right_min++] : p[temp++];

			while (temp < left_max)
				p[--right_min] = p[--left_max];

			while (next > left_min)
				p[--right_min] = tmp[--next];
		}
	}

	free(tmp);
}

void MergeSortParallel(KeyInt *p, KeyInt *temp, int l, int r)//2     
{
	int mid = (l + r) / 2;
	if (l == r)
		return;
#pragma omp parallel
	{
#pragma omp sections
	{
#pragma omp section
	{
		//printf("%d,", omp_get_num_threads());
		//printf("%d,", omp_get_thread_num());
		MergeSort(p, temp, l, mid);
	}
#pragma omp section
	{
		//printf("%d,", omp_get_num_threads());
		//printf("%d,", omp_get_thread_num());
		MergeSort(p, temp, mid + 1, r);
	}
	}
	}
	//MergeSort(p, temp, l, mid);
	//MergeSort(p, temp, mid + 1, r);
	//printf("%d,", omp_get_num_threads());

	/*for (int i = l; i <= r; i++) {
		temp[i] = p[i];
	}
	int i1 = l;
	int i2 = mid + 1;
	for (int cur = l; cur <= r; cur++) {
		if (i1 == mid + 1)
			p[cur] = temp[i2++];
		else if (i2 > r)
			p[cur] = temp[i1++];
		else if (temp[i1] < temp[i2])
			p[cur] = temp[i1++];
		else
			p[cur] = temp[i2++];
	}*/
	Merge(p, temp, l, r);
}

void MergeSortParallel(KeyInt *p, KeyInt *temp, int N)//4     
{
	int i;
	int *p1 = new int[N / 4];
	int *p11 = new int[N / 4];
	for (i = 0; i < N / 4; i++)
		p1[i] = p[i];
	int *p2 = new int[N / 4];
	int *p22 = new int[N / 4];
	for (i = 0; i < N / 4; i++)
		p2[i] = p[i+N/4];
	int *p3 = new int[N / 4];
	int *p33 = new int[N / 4];
	for (i = 0; i < N / 4; i++)
		p3[i] = p[i+N/4+N/4];
	int *p4 = new int[N - N / 4 * 3];
	int *p44 = new int[N - N / 4 * 3];
	for (i = 0; i < (N - N / 4 * 3); i++)
		p4[i] = p[i+N/4+N/4+N/4];
#pragma omp parallel
	{
#pragma omp sections
	{
#pragma omp section
	{
		MergeSort(p1, p11, 0, N / 4-1);
	}
#pragma omp section
	{
		MergeSort(p2, p22, 0, N / 4-1);
	}
#pragma omp section
	{
		MergeSort(p3, p33, 0, N / 4 - 1);
	}
#pragma omp section
	{
		MergeSort(p4, p44, 0, N - N / 4 * 3-1);
	}
	}
	}

	delete[] p11;
	delete[] p22;
	delete[] p33;
	delete[] p44;

	int* temp1 = new int[N / 4 + N / 4];
	int* temp11 = new int[N / 4 + N / 4];
	for (i = 0; i < N / 4; i++)
	{
		temp1[i] = p1[i];
		temp11[i] = p1[i];
	}
	delete[] p1;
	for (i = 0; i < N / 4; i++)
	{
		temp1[i + N / 4] = p2[i];
		temp11[i + N / 4] = p2[i];
	}
	delete[] p2;
	int* temp2 = new int[N-(N / 4 + N / 4)];
	int* temp22 = new int[N - (N / 4 + N / 4)];
	for (i = 0; i < N / 4; i++)
	{
		temp2[i] = p3[i];
		temp22[i] = p3[i];
	}
	delete[] p3;
	for (i = 0; i < (N - N / 4 * 3); i++)
	{
		temp2[i + N / 4] = p4[i];
		temp22[i + N / 4] = p4[i];
	}
	delete[] p4;
	Merge(temp1, temp11, 0, N / 4 + N / 4 - 1);
	Merge(temp2, temp22, 0, N - (N / 4 + N / 4) - 1);

	delete[] temp11;
	delete[] temp22;
	
	int* temp3 = new int[N];
	int* temp33 = new int[N];
	for (i = 0; i < N / 4 + N / 4; i++)
	{
		temp3[i] = temp1[i];
		temp33[i] = temp1[i];
	}
	delete[] temp1;
	for (i = 0; i < N - (N / 4 + N / 4); i++)
	{
		temp3[i + N / 4 + N / 4] = temp2[i];
		temp33[i + N / 4 + N / 4] = temp2[i];
	}
	delete[] temp2;
	Merge(temp3, temp33, 0, N-1);
	for (i = 0; i < N; i++)
		p[i] = temp3[i];
	delete[] temp3;
	delete[] temp33;
}

/*
 * ：
 * ： 　　
 * 1） i、j， ：i=0，j=N-1； 　　
 * 2） ， key， key=A[0]； 　　
 * 3） j ， （j=j-1 j--），
 * key A[j]，A[i] A[j] ； 　　
 * 4） i ， （i=i+1 i++），
 * key A[i]，A[i] A[j] ； 　　
 * 5） 3、4、5 ， I=J； 
 * (3,4 j=j-1，i=i+1， 。
 * i， j 。
 * i=j i+ j- 。） 
 */

void QuickSort(KeyInt *p, int low, int high)//  
{
	if (low >= high)
	{
		return;
	}
	int first = low;
	int last = high;
	int key = p[first];/*             */

	while (first < last)
	{
		while (first < last && p[last] >= key)
		{
			--last;
		}

		p[first] = p[last];/*           */

		while (first < last && p[first] <= key)
		{
			++first;
		}

		p[last] = p[first];
		/*           */
	}
	p[first] = key;/*      */
	QuickSort(p, low, first - 1);
	QuickSort(p, first + 1, high);
}

void QuickSortAverage(KeyInt *p, int low, int high)//  +    +  
{
	if (high - low + 1 < 20)
	{
		InsertSort(p, low, high);
		return;
	}//else ，      
	int first = low;
	int last = high;
	//int key = p[first];/*             */
	int key = SelectPivotMedianOfThree(p, low, high);

	while (first < last)
	{
		while (first < last && p[last] >= key)
		{
			--last;
		}

		p[first] = p[last];/*           */

		while (first < last && p[first] <= key)
		{
			++first;
		}

		p[last] = p[first];
		/*           */
	}
	p[first] = key;/*      */
	QuickSortAverage(p, low, first - 1);
	QuickSortAverage(p, first + 1, high);
}

void QuickSortSame(KeyInt *p, int low, int high)//  +    +  +      
{
	if (high - low + 1 < 20)
	{
		InsertSort(p, low, high);
		return;
	}
	int temp;
	int first = low;
	int last = high;

	int left = low;
	int right = high;

	int leftLen = 0;
	int rightLen = 0;


	//      
	int key = SelectPivotMedianOfThree(p, low, high);//             

	while (low < high)
	{
		while (high > low && p[high] >= key)
		{
			if (p[high] == key)//        
			{
				//swap(p[right], p[high]);
				temp = p[right];
				p[right] = p[high];
				p[high] = temp;
				right--;
				rightLen++;
			}
			high--;
		}
		p[low] = p[high];
		while (high > low && p[low] <= key)
		{
			if (p[low] == key)
			{
				//swap(p[left], p[low]);
				temp = p[left];
				p[left] = p[low];
				p[low] = temp;
				left++;
				leftLen++;
			}
			low++;
		}
		p[high] = p[low];
	}
	p[low] = key;

	//        
	//    key                 
	int i = low - 1;
	int j = first;
	while (j < left && p[i] != key)
	{
		//swap(p[i], p[j]);
		temp = p[i];
		p[i] = p[j];
		p[j] = temp;
		i--;
		j++;
	}
	i = low + 1;
	j = last;
	while (j > right && p[i] != key)
	{
		//swap(p[i], p[j]);
		temp = p[i];
		p[i] = p[j];
		p[j] = temp;
		i++;
		j--;
	}
	QuickSortSame(p, first, low - 1 - leftLen);
	QuickSortSame(p, low + 1 + rightLen, last);
}

void QuickSortParallel(KeyInt *p, int low, int high)//2   
{
	p[0] = BOUNDARY / 2;
	/*for (int i = low; i <= high; i++)
	{
		if (abs(p[i] - BOUNDARY / 2) < 10)
		{
			int temp = p[i];
			p[i] = p[0];
			p[0] = temp;
			break;
		}
	}*/
	int mid = Partition(p, low, high);
#pragma omp parallel
{
#pragma omp sections
{
#pragma omp section
{
	QuickSortAverage(p, low, mid-1);
}
#pragma omp section
{
	QuickSortAverage(p, mid+1, high);
}
}
}
}

void QuickSortParallel4Core(KeyInt *p, int low, int high)//4   
{
	p[0] = BOUNDARY / 2;
	/*for (int i = low; i <= high; i++)
	{
		if (abs(p[i] - BOUNDARY / 2) < 10)
		{
			int temp = p[i];
			p[i] = p[0];
			p[0] = temp;
			break;
		}
	}*/
	int mid = Partition(p, low, high);
	p[low] = BOUNDARY / 4;
	int quarter1 = Partition(p, low, mid - 1);
	p[mid + 1] = BOUNDARY / 4 * 3;
	int quarter2 = Partition(p, mid + 1, high);
#pragma omp parallel
	{
#pragma omp sections
	{
#pragma omp section
	{
		//double start1 = omp_get_wtime();
		QuickSortAverage(p, low, quarter1-1);
		//double end1 = omp_get_wtime();
		//printf("%lf
", end1 - start1);
	}
#pragma omp section
	{
		//double start2 = omp_get_wtime();
		QuickSortAverage(p, quarter1 + 1, mid-1);
		//double end2 = omp_get_wtime();
		//printf("%lf
", end2 - start2);
	}
#pragma omp section
	{
		//double start3 = omp_get_wtime();
		QuickSortAverage(p, mid+1, quarter2-1);
		//double end3 = omp_get_wtime();
		//printf("%lf
", end3 - start3);
	}
#pragma omp section
	{
		//double start4 = omp_get_wtime();
		QuickSortAverage(p, quarter2+1, high);
		//double end4 = omp_get_wtime();
		//printf("%lf
", end4 - start4);
	}
	}
	}
}

/*    ：       low、mid、high       ，               */
int SelectPivotMedianOfThree(int *arr, int low, int high)//    
{
	int temp;
	int mid = low + ((high - low) >> 1);//              

										//             
	if (arr[mid] > arr[high])//  : arr[mid] <= arr[high]  
	{
		//swap(arr[mid], arr[high]);
		temp = arr[mid];
		arr[mid] = arr[high];
		arr[high] = temp;
	}
	if (arr[low] > arr[high])//  : arr[low] <= arr[high]  
	{
		//swap(arr[low], arr[high]);
		temp = arr[low];
		arr[low] = arr[high];
		arr[high] = temp;
	}
	if (arr[mid] > arr[low]) //  : arr[low] >= arr[mid]  
	{
		//swap(arr[mid], arr[low]);
		temp = arr[mid];
		arr[mid] = arr[low];
		arr[low] = temp;
	}
	//  ，arr[mid] <= arr[low] <= arr[high]  
	return arr[low];
	//low                 
	//         low         ，            
}

int Partition(int * a, int low, int high)//  
{
	int pivotkey = a[low];
	while (low= pivotkey)
			--high;
		a[low] = a[high];
		while (low regions;//         
	Region region;
	region.low = 0;
	region.high = len - 1;
	regions.push(region);
	while (!regions.empty())
	{
		region = regions.top();
		regions.pop();
		int p = Partition(a, region.low, region.high);
		if (p - 1>region.low)
		{
			Region regionlow;
			regionlow.low = region.low;
			regionlow.high = p - 1;
			regions.push(regionlow);
		}
		if (p + 1

KeyInt* randomCreate(int N) {
	int i = 0;
	KeyInt *p;
	p =(KeyInt*) malloc(N * sizeof(KeyInt));

	for (i = 0; i < N; i++)
		p[i] = myrandom(BOUNDARY);
		//p[i] = random(BOUNDARY);
	return (p);
}

bool happened(double probability)//probability 0~1
{
	if (probability <= 0)
	{
		return false;
	}
	if (probability R)
		{
			t = rand();
		}
		return t % n;
	}
	else
	{
		int r = n % (RAND_MAX + 1);//  
		if (happened((double)r / n))//       
		{
			return n - r + myrandom(r);
		}
		else
		{
			return rand() + myrandom(n / (RAND_MAX + 1))*(RAND_MAX + 1);
		}
	}
}

void DisPlay(int N, KeyInt *p)
{
	for (int i = 0; i < 100; i++)
		printf("%d
", p[i]);
}

rand() ， 。 ,rand() ， 0~2^15-1(32767)， 。 rand() ， myrandom() ， 0~n-1 。

：

1： CPU ， CPU 。

2： ， ， CPU ， ， CPU 。 CPU 。 。 ， CPU 。

3： ， ， ， 。

4： ， ， ， ， 。

， ， 。