nbpx.txt

对十种内部排序的比较．有直接排序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <windows.h>
#include <winbase.h>
#define MAXSIZE 100
#define TRUE 1
#define FALSE 0
#define D 5
#define R 10                      /* R为基数 */
typedef int BOOL;
 struct RedType{
  int key;
  struct RedType *link;
};
 struct LinkList{
  RedType r[MAXSIZE+1];
  int Length;
  
};

int RandArray[MAXSIZE+1];

void RandomNum(){
  int i;
  srand(2000);
  for (i = 1; i <= MAXSIZE; i++)
	  RandArray[i] = (int)rand();
}

void InitLinkList(LinkList *L){
  int i;
  memset(L, 0, sizeof(LinkList));
  RandomNum();
  for (i = 1; i <= MAXSIZE; i++)
    L->r[i].key = RandArray[i];
  L->Length = i;
}

bool LT(int i, int j, int *CmpNum){
  (*CmpNum)++;
  if (i < j)
    return TRUE;
  else
    return FALSE;
}

void Display(LinkList *L){
  FILE *f1;
  int i;
  if ((f1 = fopen("Input.txt", "w")) == NULL){
    printf("can't open file\n");
    exit(0);
  }
  for (i = 0; i < L->Length; i++)
    fprintf(f1, " %d", L->r[i].key);
  fclose(f1);
}

//希尔排序
void ShellInsert(LinkList *L, int dk, int *CmpNum, int *ChgNum){
  int i, j;
  RedType Temp;
  for (i = dk; i < L->Length; i++){
    if (LT(L->r[i].key, L->r[i - dk].key, CmpNum)){
      memcpy(&Temp, &L->r[i], sizeof(RedType));
      for (j = i - dk; j >= 0 && LT(Temp.key, L->r[j].key, CmpNum); j -= dk){
        (*ChgNum)++;
        memcpy(&L->r[j + dk], &L->r[j], sizeof(RedType));
      }
      memcpy(&L->r[j + dk], &Temp, sizeof(RedType));
    }
  }
}
void ShellSort(LinkList *L, int dlta[], int t, int *CmpNum, int *ChgNum){
  int k;
  
  
  for (k = 0; k < t; k++)
   ShellInsert(L, dlta[k], CmpNum, ChgNum);
 
 
  
}
  
  

//快速排序
int Partition(LinkList *L, int low, int high, int *CmpNum, int *ChgNum){
  RedType Temp;
  int PivotKey;
  memcpy(&Temp, &L->r[low], sizeof(RedType));
  PivotKey = L->r[low].key;
  while (low < high){
    while (low < high && L->r[high].key >= PivotKey){
      high--;
      (*CmpNum)++;
    }
    (*ChgNum)++;
    memcpy(&L->r[low], &L->r[high], sizeof(RedType));
    while (low < high && L->r[low].key <= PivotKey){
      low++;
      (*CmpNum)++;
    }
    (*ChgNum)++;
    memcpy(&L->r[high], &L->r[low], sizeof(RedType));
  }
  memcpy(&L->r[low], &Temp, sizeof(RedType));
  return low;
}
void QSort(LinkList *L, int low, int high, int *CmpNum, int *ChgNum){
  int PivotLoc = 0;
  if (low < high){
    PivotLoc = Partition(L, low, high, CmpNum, ChgNum);
    QSort(L, low, PivotLoc - 1, CmpNum, ChgNum);
    QSort(L, PivotLoc + 1, high, CmpNum, ChgNum);
  }
}
void QuickSort(LinkList *L, int *CmpNum, int *ChgNum){
  QSort(L, 0, L->Length - 1, CmpNum, ChgNum);
}

//堆排序
void HeapAdjust(LinkList *L, int s, int m, int *CmpNum, int *ChgNum){
  RedType Temp;
  int j = 0;
  s++;
  memcpy(&Temp, &L->r[s - 1], sizeof(RedType));
  for (j = 2 * s; j <= m; j *= 2){
    if (j < m && LT(L->r[j - 1].key, L->r[j].key, CmpNum))
      ++j;
    if (!LT(Temp.key, L->r[j - 1].key, CmpNum))
      break;
    (*ChgNum)++;
    memcpy(&L->r[s - 1], &L->r[j - 1], sizeof(RedType));
    s = j;
  }
  memcpy(&L->r[s - 1], &Temp, sizeof(RedType));
}
void HeapSort(LinkList *L, int *CmpNum, int *ChgNum){
  int i = 0;
  RedType Temp;
  for (i = L->Length / 2-1; i >= 0; i--)
    HeapAdjust(L, i, L->Length, CmpNum, ChgNum);
  for (i = L->Length; i > 1; i--){
    memcpy(&Temp, &L->r[0], sizeof(RedType));
    (*ChgNum)++;
    memcpy(&L->r[0], &L->r[i - 1], sizeof(RedType));
    memcpy(&L->r[i - 1], &Temp, sizeof(RedType));
    HeapAdjust(L, 0, i - 1, CmpNum, ChgNum);
  }
}

//冒泡排序
void BubbleSort(LinkList *L, int *CmpNum, int *ChgNum){
  int i, j;
  RedType temp;
  for (i = 1; i <= MAXSIZE; i++){
    for (j = 1; j <= MAXSIZE - i; j++){
      if (!LT(L->r[j].key, L->r[j + 1].key, CmpNum)){
        (*ChgNum)++;
        memcpy(&temp, &L->r[j], sizeof(RedType));
        memcpy(&L->r[j], &L->r[j + 1], sizeof(RedType));
        memcpy(&L->r[j + 1], &temp, sizeof(RedType));
      }
    }
  }
}

//选择排序
int SelectMinKey(LinkList *L, int k, int *CmpNum){
  int Min = k;
  for (; k < L->Length; k++){
    if (!LT(L->r[Min].key, L->r[k].key, CmpNum))
      Min = k;
  }
  return Min;
}
void SelSort(LinkList *L, int *CmpNum, int *ChgNum){
  int i, j;
  RedType temp;
  for (i = 0; i < L->Length; i++){
    j = SelectMinKey(L, i, CmpNum);
    if (i != j){
      (*ChgNum)++;
      memcpy(&temp, &L->r[i], sizeof(RedType));
      memcpy(&L->r[i], &L->r[j], sizeof(RedType));
      memcpy(&L->r[j], &temp, sizeof(RedType));
    }
  }
}
//折半插入
void BInsertSort(LinkList *L,int *CmpNum, int *ChgNum){
  RedType Temp;
  int low,high,i,j,m;
  for(i=2;i<=MAXSIZE;++i){
  memcpy(&Temp, &L->r[i], sizeof(RedType));
  low=1;high=i-1;
  while (low <= high){
   m=(low+high)/2;
  if (LT(Temp.key, L->r[m].key, CmpNum))
   high=m-1;
   else low=m+1;
   }
   for(j=i-1;j>=high+1;--j){
   (*ChgNum)++; 
   memcpy(&L->r[j+1], &L->r[j], sizeof(RedType));}
   memcpy(&L->r[high+1], &Temp, sizeof(RedType));
   } 
}
//归并排序
void Merge(LinkList *L,int low,int mid,int high,int *CmpNum,int *ChgNum){
  int begin1,begin2,s;
  int *temp=new int[high-low+1];
   begin1=low;     
   begin2 =mid+1;
   s=0;
     while(begin1<= mid && begin2<=high)
                if(LT(L->r[begin1].key,L->r[begin2].key,CmpNum))
                { 
                     temp[s++]=L->r[begin1++].key;  
                    
                  (*ChgNum)++;
                }
                else
                {    (*CmpNum)++;
                    temp[s++]=L->r[begin2++].key;  
					   
                        (*ChgNum)++;
                }
                           
        
        while(begin1<=mid) 
        {
               temp[s++]=L->r[begin1++].key; 
			  
			   (*ChgNum)++;

        }
        while(begin2<=high)
        {
               temp[s++]=L->r[begin2++].key; 
			 
			   (*ChgNum)++;  
        }
        for (s = 0; s<=high-low; s++) 
             L->r[low+s].key=temp[s];  
       
}
void MSort(LinkList *L,int low,int high, int *CmpNum,int *ChgNum){
  if(low<high)    
      {  
		int mid=(low+high)/2; //找出中点，准备折半处理      
        MSort(L,low,mid,CmpNum,ChgNum); //递归处理前一半序列,使其有序      
        MSort(L,mid+1,high,CmpNum,ChgNum); //递归处理后一半序列,使其有序      
        Merge(L,low,mid,high,CmpNum,ChgNum); //合并前后两个有序序列       
    }
}
void MergeSort(LinkList *L, int *CmpNum, int *ChgNum){
 MSort(L,1,MAXSIZE,CmpNum,ChgNum);
}
        
//基数排序 

//基数排序 
void bases(RedType **h,int *CmpNum, int *ChgNum){
    RedType *head[10],*tail[10],*p,*u;
    int factor=1,i,j;
	 p=*h;
    for(i=0;i<D;i++)
   {
   for(j=0;j<10;j++)
   {head[j]=NULL;
    tail[j]=NULL;
   }
     while(p)
   {
      u=p->link;
         j=(p->key/factor)%10;
   if(head[j]==NULL)
   head[j]=p;
   else
    tail[j]->link=p;
   tail[j]=p;
   tail[j]->link=NULL;
   (*CmpNum)++;
   p=u;
   }
   p=NULL;
   for(j=0;j<10;j++)
   {
      if(head[j]==NULL)
    continue;
   if(p==NULL)
    p=head[j];
   else
    u->link=head[j];
   u=tail[j];
   }
  factor*=10;

   }
    *h=p;
	
}
void RadixSort(LinkList *L,int *CmpNum, int *ChgNum){
   int i;
   int a;
   RedType *h,*k;
   int *temp=new int[MAXSIZE];
   h=NULL;
   
  
   for(i=1;i<=MAXSIZE;++i)
   { temp[i]=L->r[i].key;
   }
   for(int j=1;j<=MAXSIZE;++j)
   {
	   k=new(RedType);
    k->key=temp[j];
     k->link=h; 
     h=k; 
   } 
     
     bases(&h,CmpNum,ChgNum);
   
   for(a=1,k=h;k,a<=MAXSIZE;k=k->link,a++)
   {   temp[a]=k->key;
       L->r[a].key=temp[a];     
   }
}

  

//二路插入排序
void InsertSortBinary(LinkList *L,int *CmpNum, int *ChgNum){
	    int q=0,num=0;
        int *temp=new int[MAXSIZE]; //分配辅助空间   
        temp[1]=L->r[1].key; //第一个元素直接放入辅助数组，形成初始的有序表   
        int first=1, last=1; //有序表首元和尾元的下标 
        for(int i=2; i<=MAXSIZE; i++) //从第二个元素起依次做插入排序   
        {  
			if(LT(L->r[i].key,temp[1], CmpNum)) 
			{ //新插元素比有序表中间元素还小 
              for(int j=first; temp[j]<=L->r[i].key; j=(j+1)%MAXSIZE )
			  {
				  (*CmpNum)++;
                  temp[(j-1+MAXSIZE)%MAXSIZE]=temp[j];
			  }
              temp[(j-1+MAXSIZE)%MAXSIZE]=L->r[i].key; //插入待插元素         
              first=(first-1+MAXSIZE)%MAXSIZE;      
            }
			else 
			{ //新插元素比有序表表中间元素还大