bubblesort.cpp

实现排序算法中的冒泡排序过程 并在最坏和平均状况下加以对比

//冒泡排序程序，非递减排序
//测试集为(0,100)浮点数
//n=10000
//冒泡排序时间:平均为1.859s，最坏3.015s

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

#define MAXSIZE 10000   //最大数组长度

int flag;
double sorttime;

//初始化序列
void InitArray(double *a)
{
	
	if(flag==0)  //随机数进行初始化
	{
		srand((unsigned)time(NULL)); //产生以当前时间开始的随机种子

		for(int i=1;i<MAXSIZE+1;i++)
			a[i]=rand()/(double)(RAND_MAX/100);    //(0,100)浮点数 
	}
	else        //逆序排列，最坏情况
	{
		a[1]=100;
		for(int i=2;i<MAXSIZE+1;i++)
			a[i]=a[i-1]-0.01;
	}

}

//打印序列
void DispArray(double *a,FILE *file)
{  
	for(int i=1;i<MAXSIZE+1;i++)
	{
		fprintf(file,"%-12lf",a[i]);
		if(!(i%10))
			fprintf(file,"\n");
	}

	fprintf(file,"\n");
}

//对序列进行冒泡排序，非递减顺序
void BubbleSort(double *a)
{
	clock_t start,finish;

	start=clock();
	
	for(int i=1,switchnum=1;(i<MAXSIZE+1)&&(switchnum>0);i++)//i记录排序趟数 switchnum记录交换次数
	{
		switchnum=0;
		for(int j=1;j<MAXSIZE-i+1;++j)  //避免越界
			if(a[j]>a[j+1])
			{
				double temp;
				
				temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
				
				++switchnum;
			}
	}

	finish=clock();

	sorttime=(double)(finish-start)/CLOCKS_PER_SEC; 

}

void main()
{
	double array[MAXSIZE+1]; //array[0]闲置或用作哨兵单元

	flag=0; 
	InitArray(array);

	FILE *fpr;

    if((fpr=fopen("result.txt","w"))==NULL)  //打开只写文件，无则创建
	{
		printf("open result file failed!\n");
		perror("open"); 	
		exit(1);
	}
   
	fprintf(fpr,"the array before sorting in average situation:\n");
	DispArray(array,fpr);

	BubbleSort(array); //A(n)随机情况

	fprintf(fpr,"the array after sorting in average situation:\n");
	DispArray(array,fpr);  

	fprintf(fpr,"bubble sort time in average situation:%lfs\n",sorttime);

	flag=1;
   	InitArray(array);

	fprintf(fpr,"the array before sorting in the worst situation:\n");
	DispArray(array,fpr);

	BubbleSort(array); //W(n)最坏情况

	fprintf(fpr,"the array after sorting in the worst situation:\n");
	DispArray(array,fpr);  
	
	fprintf(fpr,"bubble sort time in the worst situation:%lfs\n",sorttime);

	fclose(fpr);
}