qhncxf_paixu.h

这是一个排序算法的应用

#include <stdlib.h>
#include <stdio.h>
//顺序表表示的存储结构
#define MAXNUM 100000
typedef int KeyType;
typedef int DataType;
typedef struct      
{                    
  KeyType key;        //排序码字段
  DataType info;      //记录的其他字段
}RecordNode;
typedef struct
{
  RecordNode record[MAXNUM];
  int n;              //n为文件中的记录个数，n<=MAXNUM
}SortObject;
/**************************************************/
/*                Shell插入排序算法               */
/**************************************************/  
void shellSort(SortObject &pvector,int &com,int &mov)
{
   int i,j,increment;
    RecordNode temp;
     for(increment=4;increment>0;increment/=2)
      /*increment 为本趟Shell排序增量*/
      {
        for(i=increment;i<pvector.n;i++)
        {
		   
           temp=pvector.record[i];    /*保存待插入记录Ri*/
           j=i-increment;
		   com++;
           while(j>=0&&temp.key<pvector.record[j].key)  /*查找插入位置*/
           {  
			  mov++;
              pvector.record[j+increment]=pvector.record[j]; /*记录后移*/
              j-=increment;
			  if(j>=0)
			    com++;
           }
           pvector.record[j+increment]=temp;/*插入记录Ri*/
        }
      }
}
/******************************************/
/*               堆排序算法               */
/******************************************/
/*筛选算法*/
#define leftChild(i) 2*(i)+1
void sift(SortObject &pvector,int i,int n,int &com,int &mov)
{
   int child;
   RecordNode temp;
   temp=pvector.record[i];
   child=leftChild(i);/*Rchild是R0的左子女*/
   while(child<n)
   {
      if(child<n-1)
	  {   com++;
		  if(pvector.record[child].key<pvector.record[child+1].key)
            child++;/*child指向Ri的左、右子女中排序码较大的结点*/
	  }
	   com++;
      if(temp.key<pvector.record[child].key)
      {
         pvector.record[i]=pvector.record[child];
         /*将Rchild换到父结点位置，进入下一层继续调整*/
		 mov++;
         i=child;
         child=leftChild(i);
      }
      else break;/*调整结束*/
   }
   pvector.record[i]=temp;/*将记录Ri放入正确位置*/
}
/*堆排序算法*/
void heapSort(SortObject &pvector,int &C,int &M) /*对记录R0到Rn-1进行堆排序*/
{
   int i,n;
   RecordNode temp;
   n=pvector.n;
   for(i=n/2-1;i>=0;i--)
     sift(pvector,i,n,C,M);  /*建立初始堆*/
   for(i=n-1;i>0;i--)    /*进行n-1趟堆排序*/
   {
	   M++;
      temp=pvector.record[0];  /*当前堆顶记录和最后一个记录互换*/
      pvector.record[0]=pvector.record[i];
      pvector.record[i]=temp;
        sift(pvector,0,i,C,M) ;  /*从R0到Ri-1重建堆*/
   }
}
/*****************************************/
/*              快速排序算法             */
/*****************************************/
void quickSort(SortObject &pvector,int l,int r,int &com,int &res)
{
  int i,j;
  RecordNode temp;
  if(l>=r)
    return;/*只有一个记录或无记录，则无需排序*/
  i=l;j=r;
  temp=pvector.record[i];
  while(i!=j)
  {
	  com++;
      while((pvector.record[j].key>=temp.key)&&(j>i))
	  {
		  j--;/*从右向左扫描，查找第l个排序码小于temp.key的记录*/
		  com++;
	  }
      if(i<j)
         pvector.record[i++]=pvector.record[j];
	     res++;
		 com++;
      while((pvector.record[i].key<=temp.key)&&(j>i))
	  {
		  i++;/*从左向左扫描，查找第l个排序码大于temp.key的记录*/
		  com++;
	  }
      if(i<j)
          pvector.record[j--]=pvector.record[i];
	      res++;
  }
  pvector.record[i]=temp;    /*找到Ri的最终位置*/
  quickSort(pvector,l,i-1, com, res);  /*递归处理左区间*/
  quickSort(pvector,i+1,r,com,res);  /*递归处理右区间*/
}
/*****************************************/
/*               冒泡排序算法            */
/*****************************************/
void bubbleSort(SortObject &pvector,int &com,int &mov )
{
   int i,j,noswap;
   RecordNode temp;
   for(i=0;i<pvector.n;i++)            /*做n-1次起泡*/
   {
      noswap=TRUE;
      for(j=0;j<pvector.n-i-1;j++)    /*置交换标志*/
	  {
		com++;
        if(pvector.record[j+1].key<pvector.record[j].key) /*从前向后扫描*/
        {
		  mov++;
          temp=pvector.record[j];                        /*交换记录*/
          pvector.record[j]=pvector.record[j+1];
          pvector.record[j+1]=temp;
          noswap=FALSE;
        }
	  }
      if(noswap)
      break;  /*本趟起泡未发生记录交换，算法结束*/
   }
}
/**************************************************/
/*               二分法插入排序算法               */
/**************************************************/  
void binSort (SortObject &pvector,int &com,int &mov)
{
	int i,j,left,mid,right;
	RecordNode temp;
    for (i=1;i<pvector.n;i++)
	{
	   temp=pvector.record[i];
	   left=0;right=i-1;         //置已排序区间的下、上界初值
	   while(left<=right)
	   {
		 mid=(left+right)/2;  //mid指向已排序区间的中间位置
		 if(temp.key<pvector.record[mid].key)
		 { com++;right=mid-1;}  //插入元素应在左子区间
		 else
			left=mid+1;      //插入元素应在右子区间
	   }
	    for(j=i-1;j>=left;j--)
		{
		pvector.record[j+1]=pvector.record[j];
		mov++;
		}
	    if(left!=i) 
		pvector.record[left]=temp;//将排序码大于Ki的记录后移
	}
}
/**************************************************/
/*              直接插入排序算法                  */
/**************************************************/  
void insertSort(SortObject &pvector,int &com,int &mov)
{ int i,j;                
  RecordNode temp;               
   for(i=1;i<pvector.n;i++)     //依次插入记录R1、R2\......
  {
	  temp=pvector.record[i];
	  j=i-1;
	  com=i;
	  while((temp.key<pvector.record[j].key)&&(j>=0))//由后向前找插入位置
	  {
		  mov++;
		  pvector.record[j+1]=pvector.record[j];    //将排序码大于Ki的记录后移
		  j--;
	  }
	  if(j!=(i-1)) pvector.record[j+1]=temp;
  }
   com+=mov;
}
/*****************************************/
/*            直接选择排序算法           */
/*****************************************/
void SelectSort(SortObject &pvector,int &com,int &mov)
{
	int i,j,k;
	RecordNode temp;
	 for(i=0;i<pvector.n;i++)//做n-1趟选择排序
	 {
		 k=i;
		 for(j=i+1;j<pvector.n;j++)//在无序区内找出排序码最小的记录Rk;
		 {
			 com++;              //比较次数的统计
			 if(pvector.record[j].key<pvector.record[k].key) 
				 k=j;
		 }
		 if(k!=i)
		 {
			 mov++;               //移动次数的统计
			 temp=pvector.record[i];
			 pvector.record[i]=pvector.record[k];
			 pvector.record[k]=temp;
		 }
	 }
}