sort.cpp

利用多线程并行执行三种排序算法（冒泡排序、快速排序、归并排序）

/*
sort.cpp	exp402

包含各函数的具体定义

uuhorse

2008 年 5月 5日
*/
/************************************************************************/

#include "sort.h"

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>



void CreatList( SqList num[ ] )	//生成需要排序的数字序列 
{
	int temp;
	int size;
	printf("请输入要排序的数的个数：");
	scanf("%d",&size);
	for(int i=0;i<4;i++)
	{
		num[i].ListSize=size;
		num[i].elem=(int *)malloc( num[i].ListSize*sizeof(int ));
	}
	printf("\n\n产生的需要排序的随机数序列：\n");
	srand(time(NULL));
	while (size)
	{
		/*
		printf("请输入要排序的第%2d个数：",n+1);
		scanf("%d",&temp);*/
		size--;
		temp=rand();
		num[0].elem[size]=temp;
		num[1].elem[size]=temp;
		num[2].elem[size]=temp;
		num[3].elem[size]=temp;
		printf (" %6d ",temp );
		if ((num[0].ListSize-size)%10==0)	//每行输出10个随机数
			printf ("\n");
	}
	printf("\n\n");
}



void BubbleSort ( int R[], int n)	//冒泡排序
{
	int i,j;
	int temp;
	for (i=0; i<n-1; i++)
		for (j=n-1; j>i; j--)
			if ( R[j]<R[j-1] )
			{
				temp=R[j];
				R[j]=R[j-1];
				R[j-1]=temp;
			}
}

void QuickSort(int R[],int s,int t)	//对 R 从 s 到t 进行快速排序
{
	int i=s,j=t;
	int temp;
	if(s<t)	//区间内至少存在一个元素的情况
	{
		temp=R[s];	//用区间第一个记录作为基准
		while(i!=j)	//对 R 从 s 到t 进行一次快速排序	(从区间两端交替向中间扫描)
		{
			while(i<j && R[j]>temp)		//向左扫描，找第一个小于 temp 的 R[j]
				j--;
			if(i<j)			//找到这样的 R[j], R[i]、 R[j]交换
			{
				R[i]=R[j];
				i++;
			}

			while(i<j && R[i]<temp)		//向右扫描，找第一个大于 temp 的 R[i]
				i++;
			if(i<j)			//找到这样的 R[i], R[i]、 R[j]交换
			{
				R[j]=R[i];
				j--;
			}
		}
		R[i]=temp;
		QuickSort ( R , s , i-1 );	//对左区间进行递归排序
		QuickSort ( R , i+1 , t );	//对右区间进行递归排序
	}
}



void Merge ( int R[], int low, int mid, int high )
{
	int *R1;
	int i=low, j=mid+1, k=0; /* k是R1的下标，i、j分别为第1、2段的下标*/
	R1= (int *) malloc ( (high-low+1) * sizeof(int));
	while( i<=mid && j<=high)	//在第1段 和 第2段 均未扫描完时循环
	{
		if ( R[i]<=R[j] )	//将第1段中的比较小的记录放入 R1中
		{
			R1[k]= R[i];
			i++; k++;
		}
		else				//将第2段中的比较小的记录放入 R1中
		{
			R1[k]= R[j];
			j++; k++;
		}
	}
	while ( i<=mid )		//将第1段中未完记录复制到 R1中
	{
		R1[k]=R[i];
		i++; k++;
	}
	while ( j<=high )		//将第2段中未完记录复制到 R1中
	{
		R1[k]=R[j];
		j++; k++;
	}
	for ( k=0,i=low; i<=high; k++,i++ )		//将 R1复制回  R中
	{
		R[i]=R1[k];
	}
}

void MergeSortDC (int R[], int low, int high)
/*对R[low ... high] 进行二路归并*/
{
	int mid;
	if ( low<high )
	{
		mid=( low+high )/2;
		MergeSortDC ( R, low, mid );
		MergeSortDC ( R, mid+1, high );
		Merge ( R, low, mid, high );
	}
}

void MergeSort ( int R[], int n )	//对 长为 n 的数组 R 进行二路归并排序
{
	MergeSortDC ( R, 0, n-1);
}