常见排序算法比较.cpp

冒泡排序、鸡尾酒排序/快速排序/SOrt函数排序/插入排序/折半插入排序/二路插入排序/希尔排序/选择排序/地精排序/STL堆排序/桶排序/

#include
using namespace std;
//	传参数太费事了。。用的全局变量 
	const int maxn=500005;
	int n_search;
	int cnt1cnt2;//比较，交换计数器 
	double tcnt;//时间，单位秒 
	int a[maxn]b[maxn];//a是原数组，b是给每一个算法排序用的副本 
	
	
	//全打印数组，用于捉虫 
	void debug（int *a）{
		printf（“***********************************************\n“）;
		for（int i=1;i<=n;i++）{
			printf（“ %10d“a[i]）;
			if（i%10==0）
				putchar（‘\n‘）;
		}
		printf（“***********************************************\n“）;
	}
	
	//初始化函数，清零三个计数器，拷贝a的新副本 
	void init（）{
		for（int i=1;i<=n;i++）
			b[i]=a[i];
		cnt1=cnt2=tcnt=0;
	}
	//打印	
	void prin（）{
		printf（“排序本组%d个数据进行了%d次比较，%d次移动，花费时间%.2lf毫秒\n\n“ncnt1cnt2tcnt*1000）;
	}
	//无法统计cnt1cnt2的打印 
	void prins（）{
		printf（“排序本组%d个数据花费时间%.2lf毫秒\n\n“ntcnt*1000）;
	}
	
	//冒泡排序
	double maopao（）{
		clock_t se;
		printf（“冒泡排序:\n“）;
		s=clock（）;
		for（int i=1;i			for（int j=1;j<=n-1-i;j++）{
				cnt1++;
				if（b[j]>b[j+1]）{
					swap（b[j]b[j+1]）;
					cnt2++;
				}
			}
		e=clock（）;
		return （（double）（e-s））/CLK_TCK;
	}
	//改进冒泡 
	double maopaogai（）{
		clock_t se;
		printf（“改进冒泡排序:\n“）;
		int flag=n;
		s=clock（）;
		for（int i=1;i<=flag;i++）{
			int k=flag;
			flag=0;
			for（int j=1;j				cnt1++;
				if（b[j]>b[j+1]）{
					flag=j;
					swap（b[j]b[j+1]）;
					cnt2++;
				}
			}
		}
		e=clock（）;
		return （（double）（e-s））/CLK_TCK;
	}
	//鸡尾酒 
	double jiweijiu（）{
		clock_t se;
		printf（“鸡尾酒排序:\n“）;
		s=clock（）;
		int bot=1bou=1top=n;
		bool sw=1;
		while（sw）{
			sw=0;
			for（int i=bot;i				cnt1++;
				if（b[i]>b[i+1]）{
					cnt2++;
					swap（b[i]b[i+1]）;
					sw=1;
					bou=i;
				}
			}
			top=bou;
			for（int i=top;i>bot;i--）{
				cnt1++;
				if（b[i]					cnt2++;
					swap（b[i]b[i-1]）;
					sw=1;
					bou=i;
				}
			}
			bot=bou;
		}
		e=clock（）;
		return （（double）（e-s））/CLK_TCK;
	}
	//手写快排 
	void quicksort（int beginint end）{
		if（begin>=end）
			return ;
		int t=b[begin];
		int i=beginj=end;
		while（i			while（it）{
				cnt1++;			
				j--;
			}
			cnt1++;
			b[i]=b[j];
			cnt2++;
			while（i				i++;
				cnt1++;
			}
			cnt1++;
			b[j]=b[i];
			cnt2++;
		}
		b[i]=t;
		cnt2++;
		quicksort（begini-1）;
		quicksort（i+1end）;	
	}	
	double kuaipai（）{
		clock_t se;
		printf（“快速排序:\n“）;
		s=clock（）;
		quicksort（1n）;
		e=clock（）;
		return （（double）（e-s））/CLK_TCK;
	}
	//algorithm库sort
	double _sort（）{
		clock_t se;
		printf（“Sort函数:\n“）;
		s=clock（）;
		sort（b+1b+n+1）;
		e=clock（）;
		return （（double）（e-s））/CLK_TCK;
	}
	
	//朴素插入
	double charu（）{
		clock_t se;
		printf（“插入排序:\n“）;
		
		s=clock（）;
		for（int i=1;i			int j;
			int t=b[i+1]; 
			for（j=i;cnt1++j>=1&&t				b[j+1]=b[j];
				cnt2++;
			}
			b[j+1]=t;
			cnt2++;
		}
		e=clock（）;
		return （（double）（e-s））/CLK_TCK;
	}
	//折半插入 
	double zheban（）{
		clock_t se;
		printf（“折半插入排序:\n