新建 文本文档1.cpp

内部排序

//-----------------------------------------------
//-----------------------------------------------
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#define MAXSIZE 1000
#define MINGROUP 8
#define MAXGROUP 18
#define FALSE 0
#define TRUE 1
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 Initialization() //系统初始化
{
 printf("***          Please input the Size and Groups.          ***\n");
 scanf("%d",&size);
 if(size<100)
  size=100;
 if(size>1000)  
  size=1000;
 scanf("%d",&groups);
 if(groups<MINGROUP)
  groups=MINGROUP;
 if (groups>MAXGROUP)
  groups=MAXGROUP;
 printf("***********************************************************\n");
 printf("***            --Size=%d--     --Groups=%d--            ***\n",size,groups);
}
//----------------------------------------------------
//-----------------------------------------------
int Less(int i,int j)  //表中i元素小于j元素，返回真否则为假
{
  compcount++;
  if(data1[i]<data1[j])
  return 1;
  else
  return 0;
}//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() //复制第二个书组给第一个书组
{
 for(int i=1; i<=size; i++)
  data1[i]=data2[i];
}//CopyData
//----------------------------------------------------
void BeforeSort()           //每个排序算法在入口处调用
{
 compcount=shiftcount=0;
}//BeforeSort
//----------------------------------------------------
void RandomizeList(int s, int t)  //对可排序表进行a次打乱，a为0时表不变
{
 if(t==0)
 {
  for(int i=0; i<size; i++)
  {
   data1[i]=data2[i]=i;
  }
 }
 //Order();        ///正序
 else
 {
  for(int i=0; i<size; i++)
  {
   data1[i]=data2[i]=size-i+1;
  }
 }
 //DisOrder();     //逆序
 for(int n=1; n<=MIXSIZE[s]; n++)
 {
  int a;
  a= data1[rand()%size+1];
  data1[rand()%size+1]= data1[rand()%size+1];
  data1[rand()%size+1]=a;
 }
}//RandomizeList
//----------------------------------------------------
void BubbleSort()  //进行气泡排序,返回关键字比较次数和移动次数
{
 int swapped,a,i;
 BeforeSort();
 
 do
 {
  swapped=FALSE;
  for(i=1; i<size; i++)
  {
   a=Less(i+1,i);
   if(a)
   {
    Swap(i+1,i);
    swapped=TRUE;
   }
  }
 }
 while(swapped);
 printf("BubbleSort:\t");
 printf("compcount=%6ld\t",compcount);
 printf("shiftcount=%6ld\n",shiftcount);
 CopyData();       //复制
}//BubbleSort
//----------------------------------------------------
void InsertSort()   //进行插入排序,返回关键字比较次数和移动次数
{    
 int a,j,b;
 for(int i=2; i<=size; ++i)
 {
  a=Less(data1[i],data1[i-1]);
  if(a)
  {
   data1[0]=data1[i];
   data1[i]=data1[i-1];
   for(j=i-2; b; --j)
   {
    data1[j+1]=data1[j];
    b=Less(data1[0],data1[j]);
   }
   data1[j+1]=data1[0];
  }
 }
 printf("InsertSort:\t");
 printf("compcount=%6ld\t",compcount);
 printf("shiftcount=%6ld\n",shiftcount);
 CopyData();
}// InsertSort
//----------------------------------------------------
void SelectSort()  //进行选择排序,返回关键字比较次数和移动次数
{
 int min,a,j,i;
 BeforeSort();
 for(i=1; i<size; i++)
 {
  min=i;
  for(j=i+1; j<=size; j++)
  {
   a=Less(j,min);
   if(a)
    min=j;
  }
  if(i!=min)
   Swap(i,min);
 }
 printf("SelectSort:\t");
 printf("compcount=%6ld\t",compcount);
 printf("shiftcount=%6ld\n",shiftcount);
 CopyData();
}//SelectSort
//----------------------------------------------------
int Partition(int l,int h)    //QuickSort的辅助函数
{
 int a;
 data1[0]=data1[l];
 a=data1[l];
 while(l<h)
 {
  while(l<h && Less(a,data1[h]))
   --h;
  data1[l]=data1[h];
  shiftcount+=3;
  while(l<h && data1[l]<=a)
   ++l;
  data1[h]=data1[l];
  shiftcount+=3;
 }
 data1[l]=data1[0];
 return l;
}//Partition
//----------------------------------------------------
void QSort(int l, int h)  //QuickSort的辅助函数
{
 int pi;
 if(l<h)
 {
  pi=Partition(l,h);
  QSort(l,pi-1);
  QSort(pi+1,h);
 }
}//QSort
//----------------------------------------------------
void QuickSort()      //进行快速排序,返回关键字比较次数和移动次数
{
 BeforeSort();
 QSort(1, size);
 printf("QuickSort :\t");
 printf("compcount=%6ld\t",compcount);
 printf("shiftcount=%6ld\n",shiftcount);
 CopyData();
}//QuickSort
//----------------------------------------------------
void ShellSort() //进行希尔排序,返回关键字比较次数和移动次数
{
 int i,h,j;
 BeforeSort();
 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;
 }
 printf("ShellSort :\t");
 printf("compcount=%6ld\t",compcount);
 printf("shiftcount=%6ld\n",shiftcount);
 CopyData();
}//ShellSort
//----------------------------------------------------
void Sift(int l, int r) //堆排序的调堆函数
{
 int i,j,f,a,b;
 i=l;
 j=2*i;
 Shift(l,0);
 f=FALSE;
 Shift(l,MAXSIZE+1);
 while(j<=r && !f)
 {
  a=Less(j+1,j);
  if(j<r && a)
   j++;
  b=Less(j,0);
  if(!b)
   f=TRUE;
  else
  {
   Shift(j,i);
   i=j;
   j=2*i;
  }
 }
 Shift(MAXSIZE+1,i);
}//Shift
//----------------------------------------------------
void HeapSort()  //进行堆排序,返回关键字比较次数和移动次数
{
 int l,r;
 l=size/2;
 r=size;
 BeforeSort();
 for(; l>=1; l--)
 {
  Sift(l,size);
 }
 for(; r>=2; r--)
 {
  Swap(l,r);
  Sift(l,r-1);
 }
 printf("HeapSort  :\t");
 printf("compcount=%6ld\t",compcount);
 printf("shiftcount=%6ld\n",shiftcount);
}//HeapSort
//----------------------------------------------------
void DoData()
{
 BubbleSort();     //进行气泡排序
 InsertSort();     //进行插入排序
 SelectSort();     //进行选择排序
 QuickSort();      //进行快速排序
 ShellSort();      //进行希尔排序
 HeapSort();       //进行堆排序
}
//----------------------------------------------------
void StartSort()         //进行排序
{
 int i,j;
 
 j=groups/2;
 printf("***     -Are you srue to do this data?     ---y/n--     ***\n");
 getchar();
 c=getchar();
 if(c=='y')
 {
  printf("***********************************************************\n");
  printf("***********************************************************\n");
  printf("***     Doing the data     Please    wait...            ***\n");
  for( i=1; i<=groups; i++)  //逐组测试
  {
   if(i<j)
   {
    printf("          ==== Order %d reslut : ====\n",i);
    RandomizeList(i,0);             //对正序表作第i级打乱
   }
   else
   {
    printf("          ==== Disorder %d reslut : ====\n",i);
    RandomizeList(groups-i-1,1);    //逆序作第i级打乱
   }
   DoData();            //处理数据
  }
  printf("***********************************************************\n");
  printf("***********************************************************\n");
  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';
  }
 }
 if(c=='n')
 { 
  b=TRUE;
 }
}
//----------------------------------------------------
void main()             //主函数
{
 printf("***********************************************************\n");
    printf("***       ^_^  Welcome to use my comparer  ^_^          ***\n");
 printf("***********************************************************\n");
 printf("***         -Size(100-1000)-     -Groups(8-18)-         ***\n");
 Initialization();   //系统初始化
 StartSort();        //预备工作
 printf("\n");
 printf("***       ^_^ Welcome to use again ^_^                  ***\n");
}