test.cpp

对以下5种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序。通过随机数据比较各算法的关键字比较次数和关键字移动次数

#include "sort.h"
#include <ctime>
#include <stdio.h>
#include <windows.h>
using namespace std;

void main()
{
	int num = 100;
	LARGE_INTEGER     litmp   ;   
    LONG64		QPart1,QPart2   ;   
    double		d=0;   
	
	char choice = 'a';
	
	while(num>=0)
	{
		cout<<"请输入要排序的个数(负数:退出，0:默认值):";
		cin>>num;
		if(num<0)
			cout<<"谢谢使用!Bye!"<<endl;
		else
		{
			if (num == 0)
			{
				num = 100;
			}
			
			SeqList<int> s1(num+1),pSort(num+1),shunxu(num+1),nixu(num+1);
			
			int i,keyin=1,y=0,a=0,b=0;
			srand((unsigned)time(NULL));
			
			while(s1.IsFull()==0)
			{
				i = rand();
				if(i>0)
				{			
					s1.Insert(i,keyin);
					
					keyin++;
				}
			}
			
			pSort = s1;
			pSort.Bubble();
			shunxu = pSort;
			for(i=1;i<=num;i++)
			{
				nixu.Insert(pSort.data[num-i+1],i);
			}
			
			
			do
			{
				cout<<endl;
				cout<<"1.起泡排序"<<endl;
				cout<<"2.直接插入排序"<<endl;
				cout<<"3.简单选择排序"<<endl;
				cout<<"4.快速排序"<<endl;
				cout<<"5.希尔排序"<<endl;
				cout<<"6.折半插入排序"<<endl;
				cout<<"7.二路归并排序"<<endl;
				cout<<"8.堆排序"<<endl;
				cout<<"9.二路插入排序"<<endl;
				cout<<"10.打印数组"<<endl;
				cout<<"11.打印排序结果"<<endl;
				cout<<"0.退出"<<endl;
				cout<<"请选择:";
				cin>>keyin;
				cout<<endl;
				
				if(keyin == 10)
				{
					cout<<endl<<"原数组:"<<endl;

					if (choice == 'A'||choice == 'a')
					{
						s1.Print();
					}
					else if(choice == 'B'||choice == 'b')
					{
						shunxu.Print();
					}
					else if(choice == 'C'||choice == 'c')
					{
						nixu.Print();
					}
						

					cout<<endl;
				}
				else if(keyin == 11)
				{
					cout<<endl<<"排序后的数组:"<<endl;
					pSort.Print();
					cout<<endl;
				}
				else if (keyin<0||keyin>11)
				{
					cout<<"输入错误!"<<endl;
				}
				else if(keyin != 0)
				{
					cout<<"A:随机数排序"<<endl;
					cout<<"B:顺序数排序"<<endl;
					cout<<"C:逆序数排序"<<endl;
					
					cin>>choice;
					
					cout<<endl;
					
					if (choice == 'A'||choice == 'a')
					{
						pSort = s1;
					}
					else if(choice == 'B'||choice == 'b')
					{
						pSort = shunxu;
					}
					else if(choice == 'C'||choice == 'c')
					{
						pSort = nixu;
					}
					else
						cout<<"输入错误!"<<endl;					
					
					QueryPerformanceCounter(&litmp);     
					QPart1 = litmp.QuadPart;  
					
					if(keyin == 1)
					{
						pSort.Bubble();
					}
					else if(keyin == 2)
					{
						pSort.InsertSort();
					}
					else if(keyin == 3)
					{
						pSort.SelectSort();
					}
					else if(keyin == 4)
					{
						pSort.QuickSort();
					}
					else if(keyin == 5)
					{
						pSort.Shell();
					}
					else if(keyin == 6)
					{
						pSort.HalfInsertSort();
					}
					else if(keyin == 7)
					{
						pSort.MergeSort();
					}
					else if(keyin == 8)
					{
						pSort.HeapSort();
					}
					else if(keyin == 9)
					{
						pSort.BidirInsert();
					}
					
					QueryPerformanceCounter(&litmp);     
					QPart2 = litmp.QuadPart;   
					d=(double)(QPart2 - QPart1);
					cout<<"用时"<<d<<"us"<<endl<<endl;
				}
				
			}while(keyin!=0);		
		}
	}
	
}