⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 main.cpp

📁 本文档讲解了几种排序方式的优缺点。包含直接插入、希尔、直接选择、冒泡、快速、堆、二路归并等排序方式。
💻 CPP
📖 第 1 页 / 共 2 页
字号:
🔍
12 
      R[i].key=random();
	t1=clock();
	QuickSort(R,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
    
	n=200000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	QuickSort(R,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=1000000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	QuickSort(R,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
	
	n=2000000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	QuickSort(R,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

   n=100000;
	for(i=1;i<n;i++)
      R[i].key=i;
	t1=clock();
	QuickSort(R,1,n);
	t2=clock();
	cout<<setw(10)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=n-i;
	t1=clock();
	QuickSort(R,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000<<endl;

/*------------------快速排序2----------------------*/
   cout<<setw(12)<<setfill(' ')<<"快速改进:"<<setw(8);
	n=10000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	QuickSort2(R,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

 	n=20000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	QuickSort2(R,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	QuickSort2(R,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
    
	n=200000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	QuickSort2(R,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=1000000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	QuickSort2(R,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
	
	n=2000000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	QuickSort2(R,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

   n=100000;
	for(i=1;i<n;i++)
      R[i].key=i;
	t1=clock();
	QuickSort2(R,1,n);
	t2=clock();
	cout<<setw(10)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=n-i;
	t1=clock();
	QuickSort2(R,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000<<endl;

}
void fheap()
{
	//(6)堆排序
	/*--------------------------堆排序--------------------*/
    cout<<setw(12)<<setfill(' ')<<"堆排序:"<<setw(8);
	n=10000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	HeapSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=20000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	HeapSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	HeapSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
    
	n=200000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	HeapSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=1000000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	HeapSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
	
	n=2000000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	HeapSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

    n=100000;
	for(i=1;i<n;i++)
      R[i].key=i;
	t1=clock();
	HeapSort(R,n);
	t2=clock();
	cout<<setw(10)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=n-i;
	t1=clock();
	HeapSort(R,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000<<endl;
}


void fmerge()
{
	//(7)二路归并排序及改进
	/*--------------------------归并排序----------------------*/
    cout<<setw(12)<<setfill(' ')<<"归并排序:"<<setw(8);
	n=10000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
    MergeSort(R,R1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

 	n=20000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	 MergeSort(R,R1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	 MergeSort(R,R1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
    
	n=200000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	 MergeSort(R,R1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=1000000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	 MergeSort(R,R1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
	
	n=2000000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	 MergeSort(R,R1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

   n=100000;
	for(i=1;i<n;i++)
      R[i].key=i;
	t1=clock();
	 MergeSort(R,R1,n);
	t2=clock();
	cout<<setw(10)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=n-i;
	t1=clock();
	 MergeSort(R,R1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000<<endl;

/*-----------------------归并排序2--------------------*/
    cout<<setw(12)<<setfill(' ')<<"归并改进1:"<<setw(8);

	n=10000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
    MergeSort2(R,R1,n,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

 	n=20000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	MergeSort2(R,R1,n,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	MergeSort2(R,R1,n,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
    
	n=200000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	MergeSort2(R,R1,n,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

	n=1000000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	MergeSort2(R,R1,n,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;
	
	n=2000000;
	for(i=1;i<n;i++)
      R[i].key=random();
	t1=clock();
	MergeSort2(R,R1,n,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000;

   n=100000;
	for(i=1;i<n;i++)
      R[i].key=i;
	t1=clock();
	MergeSort2(R,R1,n,1,n);
	t2=clock();
	cout<<setw(10)<<setfill(' ')<<double(t2-t1)/1000;

	n=100000;
	for(i=1;i<n;i++)
      R[i].key=n-i;
	t1=clock();
	MergeSort2(R,R1,n,1,n);
	t2=clock();
	cout<<setw(8)<<setfill(' ')<<double(t2-t1)/1000<<endl;

}

void coltittle()
{
	cout<<"正在排序，请稍候......\n";
	cout<<setw(12)<<' '
	<<setw(8)<<setfill(' ')<<setiosflags(ios::left)<<"1e4"
	<<setw(8)<<setfill(' ')<<"2e4"
	<<setw(8)<<setfill(' ')<<"1e5"
	<<setw(8)<<setfill(' ')<<"2e5"
	<<setw(8)<<setfill(' ')<<"1e6"
	<<setw(8)<<setfill(' ')<<"2e6"
	<<setw(10)<<setfill(' ')<<"1e5正序"
	<<setw(8)<<setfill(' ')<<"1e5逆序"<<endl;

}
void showmenu()
{
	cout<<"  (1) 快速排序及改进排序\n";
	cout<<"  (2) 堆排序\n";
	cout<<"  (3) 二路归并排序及改进排序\n";
	cout<<"  (4) 希尔排序及改进排序\n";
	cout<<"  (5) 直接插入排序及改进排序\n";
	cout<<"  (6) 直接选择排序\n";
	cout<<"  (7) 冒泡排序及改进排序\n";
	cout<<"  (8) 1--7逐个运行(执行顺序1234567)\n";
	cout<<"  (9) 清屏并重新显示菜单\n";
	cout<<"  (0) 退出"<<endl;
}
void showme()
{
	cout<<"\n";
	cout<<"  ****************************************************************************\n";
	cout<<"  *                05-06年第二学期05秋计算机专升本数据结构作业               *\n";
	cout<<"  *                                                                          *\n";
	cout<<"  *                                                                          *\n";
	cout<<"  *       　     教学点：华工本部                                            *\n";
	cout<<"  *       　     班  级：05秋计算机专升本　                                  *\n";
	cout<<"  *      　      学  号：200514602011033                                     *\n";
	cout<<"  *     　       姓  名：张信                                                *\n";
	cout<<"  *     　       手  机：**                                                  *\n";
	cout<<"  *     　       E-mail：* QQ 36299644                                       *\n";
	cout<<"  *      　      教  师：胡圣明                                              *\n";
	cout<<"  *      　      上  交：2006年06月01日                                      *\n";
	cout<<"  *                                                                          *\n";
	cout<<"  ****************************************************************************\n";
	cout<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl;
	cout<<"                                                             按任意键进入>>"<<endl;
	system("pause");
	fflush(stdin);
	cout<<endl;
	system("cls");
}
void main()
{
	showme();
	showmenu();
waitinput:
	printf("输入选择的序号并回车:");
	gets(cflag); 
	fflush(stdin);
	if(strlen(cflag)==1)
	{
		iflag=(int)cflag[0] - 48;
		if(iflag>=0 && iflag<=9)
			cout<<"您输入了:"<<cflag[0]<<endl;
		else
			iflag=999;
	}
	else
		iflag=999;
	switch(iflag)
	{
		case 1 :
			//5快速排序
			coltittle();
			fquick();
			goto waitinput;
			break;
		case 2 :
			//6堆
			coltittle();
			fheap();
			goto waitinput;
			break;
		case 3 :
			//7二路归并 ASCII 55
			coltittle();
			fmerge();
			goto waitinput;
			break;
		case 4 :
			//2希尔排序 ASCII 50
			coltittle();
			fshell();
			goto waitinput;
			break;
		case 5 :
			//1直接插入 ASCII 49
			coltittle();
			finsert();
			goto waitinput;
			break;
		case 6 :
			//3直接选择 ASCII 51
			coltittle();
			fselect();
			goto waitinput;
			break;
		case 7 :
			//4冒泡
			coltittle();
			fbubble();
			goto waitinput;
			break;
		case 8 :	//      8 ASCII 56
			coltittle();
			//5快速排序
			fquick();
			//6堆
			fheap();
			//7二路归并
			fmerge();
			//2希尔排序
			fshell();
			//1直接插入
			finsert();
			//3直接选择
			fselect();
			//4冒泡
			fbubble();
			goto waitinput;
			break;
		case 9 :
			//9 ASCII 57
			system("cls");
			showmenu();
			goto waitinput;
			break;
		case 0 :
			//0 ASCII  48
			cout<<"\n\n*********已经退出排序程序*********"<<endl;
			delete []R;
			delete []R1;
			break;
		case 999:
			cout<<"**错误，请重新输入**："<<endl;
			goto waitinput;
			break;
		default :
			cout<<"**错误，请重新输入**："<<endl;
			goto waitinput;
			break;
		}
}
12

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -