sortdemo.h

数据结构算法之各种排序算法比较

#include "iostream.h"
#include "string.h"
#include "math.h"
#define EQ(a,b) (a==b)
#define LT(a,b) (a<b)
#define LQ(a,b) (a>b)
#define MAXSIZE 20
typedef int KeyType;
//typedef int InfoType;
typedef struct{
	KeyType key;
//	InfoType otherinfo;
}RedType;
typedef struct{
	RedType r[MAXSIZE+1];
	int length;
}SqList;
typedef SqList HeapType;


void Swap(SqList &L,int i,int j,long &shiftCount)
{RedType temp;
	temp=L.r[i];
	L.r[i]=L.r[j];
	L.r[j]=temp;
	shiftCount=shiftCount+3;
}
void Shit(SqList &L,int i,int j,long &shiftCount)
{
	L.r[i]=L.r[j];
	shiftCount++;

}
void ShellSort(SqList &L,int dlta[],int t,long &c,long &s)
{int i,j,k,dk;
 for(k=0;k<t;++k)
 {dk=dlta[k];
  for(i=dk+1;i<=L.length;++i)
  {	  if(LT(L.r[i].key,L.r[i-dk].key))
   {  s++;
	  L.r[0]=L.r[i]; 
     
    for(j=i-dk;j>0&& LT(L.r[0].key,L.r[j].key);j-=dk)//
	{  c++;
       L.r[j+dk]=L.r[j];
	   s++;
	}//for
	c++;
       L.r[j+dk]=L.r[0];
	   s++;
   }//if
  c++;
 
  }//for
 }//for
}//ShellSort
int Partition(SqList &L,int low,int high,long &c,long &s)
{//
int pivotkey;
	s++;
	L.r[0]=L.r[low];//

 pivotkey=L.r[low].key;
 while(low<high)
 {
  while(low<high&&L.r[high].key>=pivotkey) {c++;--high;}//
  c++;
  s++;
   L.r[low]=L.r[high];// 
 
 
  
  while(low<high&&L.r[low].key<=pivotkey) {c++;++low; }//
    s++;
	c++;
	L.r[high]=L.r[low];//

 }
 s++;
 L.r[low]=L.r[0];//
return low;

}
void QSort(SqList &L,int low,int high,long &c,long &s)
{int pivotloc;
if(low<high)
{
 pivotloc=Partition(L,low,high,c,s);
 QSort(L,low,pivotloc-1,c,s);
 QSort(L,pivotloc+1,high,c,s);
}
}


void HeapAdjust(HeapType &H,int s,int m,long &c2,long &s2)
{int j;
RedType rc;
rc=H.r[s];

for(j=2*s;j<=m;j*=2)
{
if(j<m &&LT(H.r[j].key,H.r[j+1].key)) {j++;}//
c2++;

if(!LT(rc.key,H.r[j].key)) {break;}//
 c2++;
  H.r[s]=H.r[j];
  s2++;
  s=j;
  }
  H.r[s]=rc;
}//HeapAdjust

void HeapSort(HeapType &H,long &c,long &s )
{int i;
//
RedType temp;
  for(i=H.length/2;i>0;--i)
	  HeapAdjust(H,i,H.length,c,s);
  for(i=H.length;i>1;--i)
   {
	temp=H.r[1];
    H.r[1]=H.r[i];
	H.r[i]=temp;
	s=s+3;
	HeapAdjust(H,1,i-1,c,s);
   }
}