数据结构《课程设计》—六种排序方法时间的比较

	
#include<bits/stdc++.h>//万能头文件
using namespace std;
typedef long long ll;
//结构体 
struct sort_time{
	string name;//排序的名字 
	int time;//排序消耗的时间 
};
bool sort_time_cmp(sort_time a,sort_time b)
{
	return a.time<b.time;
}
//1插入排序之 直接插入排序
void insert_sort(vector<int> &v,int length)
{//开动态数组 
	int i,j,tmp;//tmp中间变量 
	for(i=1;i<length;i++)//从小到大排序 
	{
		if(v[i]<v[i-1])
		{
			tmp=v[i];
			j=i-1;
			do//找v[i]的插入位置 
			{
				v[j+1]=v[j];//将数据大于v[i]的往后移动
				j--; 
			}while(j>=0&&v[j]>tmp);
			v[j+1]=tmp;//在j+1处插入v[i] 
		}
	}
}
//2插入排序之 折半插入排序
void bin_insert_sort(vector<int> &v,int length)
{
	int i,j,low,high,mid,tmp;
	for(i=1;i<length;i++)//从小到大排 
	{
		if(v[i]<v[i-1])
		{
			tmp=v[i];//给vi保存到tmp 
			low=0;
			high=i-1;
			while(low<=high)//在vi[low-high]中查找插入的位置 
			{
				mid=(low+high)>>1;//取中间位置
				if(tmp<v[mid])
				{
					high=mid-1;//插入点在左半区 
				}
				else
				{
					low=mid+1;//插入点在右半区 
				}
			}//找位置high 
		    for(j=i-1;j>=high+1;j--)//集中进行元素向后移动 
		    {
			    v[j+1]=v[j];
		    }
		    v[high+1]=tmp;//插入tmp 
	    }
	}
}
//3希尔排序
void shell_sort(vector<int> &v,int length)
{
	int d=1;
	while(d<length/3)//设置增量 
		d=3*d+1;
	while(d>=1)
	{
		for(int i=d;i<length;i++)
		{
			for(int j=i;j>=d&&v[j]<v[j-d];j-=d)
			{
				swap(v[j],v[j-d]);//交换函数 
			}
		}
		d/=3;// d=d/3减小增量 
	}
}
//4冒泡排序
void bubble_sort(vector<int> &v,int length)
{
	bool flag;
	for(int i=0;i<length;i++)
	{
		flag=false;//刚开始变为假 
		for(int j=length-1;j>i;j--)//归为v[i]，循环length-i-1次 
		{
			if(v[j]<v[j-1])//相邻两个元素反序 
			{
				swap(v[j],v[j-1]);//交换v[j] 和v[j-1] 
				flag=true;//一旦有交换，flag变为真 
			}
		}
		if(!flag)//没有发生交换，结束返回 
		{
			return;
		}
	}
}
//5快速排序
void quick_sort(vector<int> &v,int l,int r)
{
	if(l>=r)
	return;
	int tmp=v[ (l+r) >>1 ],i=l-1,j=r+1;
	while(i<j)
	{
		do{
			i++;
		}while(v[i]<tmp);//从左向右扫描，找一个大于tmp的v[i] 
		do{
			j--;
		}while(v[j]>tmp);//从右向左扫描，找一个小于tmp的v[j] 
	    if(i<j)
		swap(v[i],v[j]);//交换台语tmp的v[i]和小于tmp的v[j] 
	}
	quick_sort(v,l,j);//对左区间递归排序 
	quick_sort(v,j+1,r);//对右区间递归排序 
}
//6选择排序
void select_sort(vector<int> &v,int length)
{//从小到大排 
	for(int i=0;i<length-1;i++)
	{
		for(int j=i+1;j<length;j++)
		{
			if(v[i]>v[j])
			   swap(v[i],v[j]);//交换 
		}
	}
}
//7堆排序
//(1)构造大根堆 
void sift(vector<int> &v,int low,int high)
{
	int i=low,j=2*i+1;//v[j]是v[i]的左孩子
	int tmp=v[i];
	while(j<=high)
	{
		if(j+1<=high&&v[j]<v[j+1])
		{
			j++;//若右孩子比较大，把 j 指向右孩子 
		}
		if(v[i]>v[j])
		{
			break;//若根节点大于等于最大孩子，则筛选结束 
		}
		else//若根节点小于最大孩子的关键字 
		{
			swap(v[i],v[j]);//将v[i]调整到双亲结点的位置上 
			i=j;//修改i和j的值，以便继续向下筛选 
			j=i*2+1; 
		}
	}
	v[i]=tmp;//被筛选结点放入最终位置 
}
//堆排序
void heap_sort(vector<int> &v,int length)
{
	for(int i=(length>>1)-1;i>=0;i--)
	{
		sift(v,i,length-1);
	}
	for(int i=length-1;i>=0;i--)
	{
		swap(v[0],v[i]);//将最后一个元素与根v[1]交换 
		sift(v,1,i-1);//对v[1--i-1]进行筛选，得到i-1个结点的堆 
	}
}
int main()
{
	srand((unsigned)time(NULL));//产生随机数的函数 
	int length;//随机数
	cout<<"输入产生随机数的个数n:"<<endl;
	cin>>length;
	//开动态数组，存随机数
	vector<int> print,insert_array, bin_insert_array, shell_array, bubble_array, quick_array, select_array, heap_array;
	for(int i=0;i<length;i++)//产生随机数的过程 
	{
		int t=rand();
		insert_array.push_back(t);
		bin_insert_array.push_back(t);
		shell_array.push_back(t);
		bubble_array.push_back(t);
		quick_array.push_back(t);
		select_array.push_back(t);
		heap_array.push_back(t);
		print.push_back(t);
	}
	cout<<"产生n个随机数如下:"<<endl;
	for(int i=0;i<length;i++)
	{
		cout<<print[i]<<" ";
	}
	cout<<endl;
	cout << "随机数生成完毕!\n开始进行排序...\n";
    clock_t start;      //定时器
    sort_time st[8];
    start = clock();
    insert_sort(insert_array, insert_array.size());
    st[0].name = "直接插入排序", st[0].time = clock() - start;
    start = clock();
    bin_insert_sort(bin_insert_array, bin_insert_array.size());
    st[1].name = "折半插入排序", st[1].time = clock() - start;
    start = clock();
    shell_sort(shell_array, shell_array.size());
    st[2].name = "希尔排序", st[2].time = clock() - start;
    start = clock();
    bubble_sort(bubble_array, bubble_array.size());
    st[3].name = "冒泡排序", st[3].time = clock() - start;
    start = clock();
    quick_sort(quick_array, 0, quick_array.size() - 1);
    st[4].name = "快速排序", st[4].time = clock() - start;
    start = clock();
    select_sort(select_array, select_array.size());
    st[5].name = "选择排序", st[5].time = clock() - start;
    start = clock();
    heap_sort(heap_array, heap_array.size());
    st[6].name = "堆排序", st[6].time = clock() - start;
	cout<<"直接插入排序结果:"<<endl;
    for(int i=0;i<length;i++)
		cout<<insert_array[i]<<" ";
	cout<<endl;
	cout<<"折半插入排序结果:"<<endl;
	for(int i=0;i<length;i++)
		cout<<bin_insert_array[i]<<" ";
	cout<<endl;
	cout<<"希尔排序结果:"<<endl;
	for(int i=0;i<length;i++)
		cout<<shell_array[i]<<" ";
	cout<<endl;
	
	cout<<"冒泡排序结果:"<<endl;
	for(int i=0;i<length;i++)
		cout<<bubble_array[i]<<" ";
	cout<<endl;
	cout<<"快速排序结果:"<<endl;
	for(int i=0;i<length;i++)
		cout<<quick_array[i]<<" ";
	cout<<endl;
	cout<<"选择排序结果:"<<endl;
	for(int i=0;i<length;i++)
		cout<<select_array[i]<<" ";
	cout<<endl;
	cout<<"堆排序结果:"<<endl;
	for(int i=0;i<length;i++)
		cout<<heap_array[i]<<" ";
	cout<<endl;
    sort(st, st + 8, sort_time_cmp);
    cout<<"第一快的排序方法:"<<st[0].name<<"时间消耗:"<<st[0].time<<"ms\n";
    cout<<"第二快的排序方法:"<<st[1].name<<"时间消耗:"<<st[1].time<<"ms\n";
    cout<<"第三快的排序方法:"<<st[2].name<<"时间消耗:"<<st[2].time<<"ms\n";
	cout<<"第四快的排序方法:"<<st[3].name<<"时间消耗:"<<st[3].time<<"ms\n";
	cout<<"第五快的排序方法:"<<st[4].name<<"时间消耗:"<<st[4].time<<"ms\n";
	cout<<"第六快的排序方法:"<<st[5].name<<"时间消耗:"<<st[5].time<<"ms\n";
	cout<<"第七快的排序方法:"<<st[6].name<<"时间消耗:"<<st[6].time<<"ms\n";
	return 0;
}