paixu.cpp

内部排序算法比较 排序算法是数据结构学科经典的内容

// paixu.cpp : Defines the entry point for the console application.
//
#include "StdAfx.h"
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#include <windows.h>
#define MAXSIZE 10000
#define MINSIZE 100
#define MINGROUP 8
#define MAXGROUP 18
#define FALSE 0
#define TRUE 1
#define SORTNUM 6

int MIXSIZE[]={0,1,4,16,64,128,256,512,1024};//构造各级乱序表时随即交换元素个数
int compcount,shiftcount;
int size,groups;
int data1[MAXSIZE+2];
int data2[MAXSIZE+2];
int b;
char c,h;
//-----------------------------------------------


void BeforeSort()           //每个排序算法在入口处调用
{
 compcount=shiftcount=0;
}//BeforeSort
//----------------------------------------------------
void InitList(int n){
	if(n<1) size=0;
	else{
		if(n>MAXSIZE) n=MAXSIZE;
		for(int i=1;i<=n;i++) data1[i]=data2[i]=i;
		size=n;
	}compcount=shiftcount=0;
}

//-----------------------------------------------






int Less(int i,int j)  
{
  compcount++;
  return (data1[i]<data1[j]);
}//Less



//-----------------------------------------------

void Swap(int i,int j) //j交换i个和j个元素
{
 int a;
 a=data1[j];
 data1[j]=data1[i];
 data1[i]=a;
 shiftcount=shiftcount+3;    //关键字移动次数加3
}//Swap
//----------------------------------------------------

void Shift(int i, int j)
{
 data1[j]= data1[i];                                                                                                                                           
 shiftcount++;             //关键字移动次数加1
}//Shift
//----------------------------------------------------
void CopyData(int list1[MAXSIZE+2],int list2[MAXSIZE+2]) //复制
{
 for(int i=1; i<=size; i++)
  list2[i]=list1[i];
}//CopyData

void RandomizeList(int s, int t)  //对可排序表进行a次打乱，a为0时表不变
{
 if(t==0)
InitList(size);
 else
  for(int i=1; i<=size; i++)
   data1[i]=data2[i]=size-i+1;
  srand(GetTickCount());
 for(int i=1;i<=MIXSIZE[s]; i++)
 {
	 int d;int j1,j2;
	j1=rand()%size;j2=rand()%size;
	d=data1[j1];data1[j1]=data1[j2];data1[j2]=d;
 }
CopyData(data1,data2);
}//RandomizeList

//----------------------------------------------------
void BubbleSort()  //进行气泡排序,返回关键字比较次数和移动次数
{
 int swapped;long time1,time2,time;
 BeforeSort();
 time1=GetTickCount();
 do
 {
  swapped=FALSE;
  for(int i=1; i<size; i++)
   if(Less(i+1,i))
	{Swap(i+1,i);swapped=TRUE;}
 }
 while(swapped);
 time2=GetTickCount();
 time=time2-time1;
printf("BubbleSort:\t");
 printf("compcount=%6ld\t",compcount);
printf("shiftcount=%6ld\t",shiftcount);
printf("time=%6ld\n",time);
 CopyData(data2,data1);       //复制
}//BubbleSort
//----------------------------------------------------
void InsertSort()   //进行插入排序,返回关键字比较次数和移动次数
{    
 int j;long time1,time2,time;
 BeforeSort();
 time1=GetTickCount();
 for(int i=2; i<=size; ++i)
 {
 Shift(i,0);j=i-1;
 while(Less(0,j)) {Shift(j,j+1);j--;}
 Shift(0,j+1);
 }
 time2=GetTickCount();
 time=time2-time1;
printf("InsertSort:\t");
printf("compcount=%6ld\t",compcount);
 printf("shiftcount=%6ld\t",shiftcount);
 printf("time=%6ld\n",time);
 CopyData(data2,data1);  
}// InsertSort

void SelectSort()  
{
 int min,a;long time1,time2,time;
 
 BeforeSort();
 time1=GetTickCount();
 for(int i=1; i<size; i++)
 {
  min=i;
  for(int j=i+1; j<=size; j++)
  {
   if(a=Less(j,min))
    min=j;
  }
  if(i!=min)
   Swap(i,min);
 }
 time2=GetTickCount();
 time=time2-time1;
printf("SelectSort:\t");
printf("compcount=%6ld\t",compcount);
printf("shiftcount=%6ld\t",shiftcount);
printf("time=%6ld\n",time);
 CopyData(data2,data1);  
}//SelectSort

void QSort(int l, int h)  //QuickSort的辅助函数
{
 int i,j,m;
 if(l<h)
 {i=l;j=h;m=(l+h)/2;
 do{
	 while(Less(i,m)) i++;
	 while(Less(m,j)) j--;
	 if(i<=j){
		 if(m==i) m=j;
		 else if(m==j) m=i;
		 Swap(i,j); i++;j--;
	 }
 }while(i<=j);
  QSort(l,j);
  QSort(i,h);
 }
}





void QuickSort(){
	long time1,time2,time;
	BeforeSort();
	time1=GetTickCount();
	QSort(1, size);
	time2=GetTickCount();
	time=time2-time1;
	printf("QuickSort :\t");
	printf("compcount=%6ld\t",compcount);
	printf("shiftcount=%6ld\t",shiftcount);
	printf("time=%6ld\n",time);
	CopyData(data2,data1);  
}//QuickSort
//----------------------------------------------------
void ShellSort() //进行希尔排序,返回关键字比较次数和移动次数
{
	int i,h,j;long time1,time2,time;
	BeforeSort();
	time1=GetTickCount();
	i=4;
	h=1;
	while(i<=size)
		{i=i*2;h=2*h+1;}
	while(h!=0){
		i=h;
		while(i<=size){
			j=i-h;
			while(j>0 && Less(j+h,j))
				{Swap(j,j+h);j=j-h;}
			i++;
		}
		h=(h-1)/2;
	}
	time2=GetTickCount();
	time=time2-time1;
	printf("ShellSort :\t");
	printf("compcount=%6ld\t",compcount);
	printf("shiftcount=%6ld\t",shiftcount);
	printf("time=%6ld\n",time);
	CopyData(data2,data1); 
}//ShellSort
//----------------------------------------------------
void Sift(int l, int r) //堆排序的调堆函数
{
	int i,j,f;
	i=l;
	j=2*i;
	Shift(l,0);
	f=FALSE;
	Shift(l,MAXSIZE+1);
	while(j<=r&&!f)
	{
	if(j<r&&Less(j+1,j))
	j++;
	if(!Less(j,0))
		f=TRUE;
	 else
		{Shift(j,i);i=j;j=2*i;} 
	}
	 Shift(MAXSIZE+1,i);
}//Sift
//----------------------------------------------------
void HeapSort()  //进行堆排序,返回关键字比较次数和移动次数
{
 int l,r;long time1,time2,time;
 BeforeSort();
 time1=GetTickCount();
 l=size/2;
 r=size;
 
 for(;l>=1;l--)
	Sift(l,size);
 for(; r>=2; r--)
	{Swap(1,r);Sift(1,r-1);}
 time2=GetTickCount();
 time=time2-time1;
printf("HeapSort  :\t");
printf("compcount=%6ld\t",compcount);
printf("shiftcount=%6ld\t",shiftcount);
printf("time=%6ld\n",time);
CopyData(data2,data1);
}//HeapSort


void Initialization() //系统初始化
{system("cls");//清屏
 printf("		     -Size(100-10000)-     -Groups(8-18)-			\n");

 printf("		       Please input the Size and Groups.					\n");
 scanf("%d",&size);
 if(size<MINSIZE)
  size=MINSIZE;
 if(size>MAXSIZE)  
  size=MAXSIZE;
 scanf("%d",&groups);
 if(groups<MINGROUP)
  groups=MINGROUP;
 if (groups>MAXGROUP)
  groups=MAXGROUP;
 printf("***            --Size=%d--     --Groups=%d--            ***\n",size,groups);
}
//--------------------------------------------------------------------------------------
void StartSort()         //进行排序
{
 int j;
 j=groups/2;
  InitList(size);
  for(int i=0; i<groups; i++)  //逐组测试
  {
   if(i<j)
   {
    printf("          ==== Order %d reslut : ====\n",i);
    RandomizeList(i,0);             //对正序表作第i级打乱
   }
   else
   {
    printf("          ==== Order -%d reslut : ====\n",groups-i-1);
    RandomizeList(groups-i-1,1);    //逆序作第i级打乱
   }
   for(int j=0;j<SORTNUM;j++)
	switch(j){
			case 0:BubbleSort();break;     //进行气泡排序
			case 1:InsertSort();break;     //进行插入排序
			case 2:SelectSort();break;     //进行选择排序
			case 3: QuickSort();break;      //进行快速排序
			case 4: ShellSort();break;      //进行希尔排序
			case 5: HeapSort();break;	  //进行堆排序 
   }
  }
  printf("		             Again  or  Quit  ?      a/q				\n");
  getchar();
  h=getchar();
  while(h=='a')
  {
   Initialization();  
   StartSort();  
   if(b==TRUE||h=='q')
    h='q';
  }
  if(h=='q')
  {
   h='q';
  }
}

//----------------------------------------------------
void main()             //主函数
{
 Initialization();   //系统初始化
 StartSort();        //预备工作
 printf("\n");

}