sortfunc.cpp

数据结构中有关排序的所有算法

/******************************************************************************
    以下这些函数实现各种形式的内部排序，包括直接插入排序，折半插入排序，2－路插
	入排序，希尔排序，快速排序，堆排序，归并排序等操作.
	相关的存储结构定义在WORK20.H中

                                                            编写者：黄海于
										                    2002、12、6
******************************************************************************/
#include "work20.h"

/******************************************************************************
    函数：SqList *CreateSqList(void);

    功能：建立待排序序列.

    形式参数：
	      无

    函数输出：
	      指向待排序序列的起始地址
******************************************************************************/
SqList *CreateSqList(void)
{
     SqList *sq;
     int   i;
	 
	 //分配存储空间
	 sq=(SqList*)malloc(sizeof(SqList));
	 //输入序列长度
     printf("Please input sequence length:");
	 scanf("%d",&(sq->Length));
	 //给序列的每个元素分配存储空间
	 sq->r=(RedType*)malloc(sizeof(RedType)*(sq->Length+1));

	 //输入序列中的元素
	 for(i=1;i<=sq->Length;i++){
         printf("Please input Element %d==>key:",i);
	     scanf("%d",&(sq->r[i].key));	 
	 }

   //返回序列起始地址
   return sq;
}

/******************************************************************************
    函数：void InsertSort(SqList *L);

    功能：直接插入排序

    形式参数：
	      L:   指向待排序序列首址

    函数输出：
	      无
******************************************************************************/
void InsertSort(SqList *L)
{
	 int i,j;
     //从第二个元素开始，将后面的元素插入到前面的有序序列
	 for(i=2;i<=L->Length;++i){
		 //如果后面元素的关键字小于前面元素的关键字，则继续向前查找
		 if(L->r[i].key<L->r[i-1].key){
			 //复制为监视哨
			 L->r[0]=L->r[i];;
			 //元素后移
			 for(j=i-1;L->r[0].key<L->r[j].key;--j)
				 L->r[j+1]=L->r[j];
			 //实现元素插入
			 L->r[j+1]=L->r[0];
		 }
	 }

  return;
}

/******************************************************************************
    函数：void BInsertSort(SqList *L);

    功能：折半插入排序

    形式参数：
	      L:   指向待排序序列首址

    函数输出：
	      无
******************************************************************************/
void BInsertSort(SqList *L)
{
     int i,j,m,low,high;
     //从第二个元素开始插入
	 for(i=2;i<=L->Length;++i){
		 //将第i个元素复制到0号存储单元
		 L->r[0]=L->r[i];
		 //设立low和high指针
		 low=1;
		 high=i-1;
		 //如果low小于等于high指针，则查找其中间元素
		 while(low<=high){
			 m=(low+high)/2;
			 //如果比中间元素小，则往前找
			 if(L->r[0].key<L->r[m].key)
				 high=m-1;
			 //反之，往后找
			 else
				 low=m+1;
		 }

         //该元素应该插入的位置应该为high+1所在的位置，其后的元素全部后移
		 for(j=i-1;j>=high+1;--j)
			 L->r[j+1]=L->r[j];
         //插入到high+1的位置
		 L->r[high+1]=L->r[0];
	 }

   return;
}

/******************************************************************************
    函数：void TInsertSort(SqList *L);

    功能：2－路插入排序

    形式参数：
	      L:   指向待排序序列首址

    函数输出：
	      无
******************************************************************************/
void TInsertSort(SqList *L)
{
     RedType *r;
	 int i,j,first,final;
     
	 //分配临时存储空间
	 r=(RedType*)malloc(sizeof(RedType)*(L->Length+1));
	 final=1;
	 first=1;
	 r[1]=L->r[1];
	 //从第二个元素开始进行2路插入
	 for(i=2;i<=L->Length;++i){
		 //如果待插入元素比第一个元素大，则插入到从第一个元素开始到final结束的
		 //存储空间中
		 if(L->r[i].key>=r[1].key){
			 for(j=final;j>0 && r[j].key>L->r[i].key;--j)
                 r[j+1]=r[j];
			 r[j+1]=L->r[i];
			 final++;
		 }
		 //如果比第一个元素小，则插入到从first开始到序列长度之间的存储空间
		 //同时，如果是第一个元素，则直接放在最后一个存储空间
		 else{
             if(first==1){
				 first=L->Length;
				 r[first]=L->r[i];
				 continue;
			 }
			 for(j=first;j<L->Length && L->r[i].key>r[j].key;++j)
			      r[j-1]=r[j];
			 r[j-1]=L->r[i];
			 first--;
                    			 
		 }
	 }

	 //将临时空间的元素重新写回原来的存储空间中
	 for(i=1;i<=L->Length;i++){
		 L->r[i]=r[first];
		 first++;
		 if(first>L->Length)
			 first=1;
	 }
     
	 //释放临时存储空间
	 free(r);

   return;
}

/******************************************************************************
    函数：void ShellSort(SqList *L,int *dlta,int t);

    功能：希尔插入排序

    形式参数：
	      L:     指向待排序序列首址
		  dlta:  希尔排序子序列中元素增量所在的存储空间首地址
		  t:     元素增量的个数

    函数输出：
	      无
******************************************************************************/
void ShellSort(SqList *L, int *dlta, int t)
{
     int k;
	 //根据每次增量进行希尔插入排序
     for(k=0;k<t;++k)
		 ShellInsert(L,dlta[k]);

   return;
}

/******************************************************************************
    函数：void ShellInsert(SqList *L, int dk);

    功能：根据dk的大小，将当前位置后dk大小的元素插入到当前位置前的子序列中

    形式参数：
	      L:     指向待排序序列首址
		  dk:    子序列中每个元素之间的相对位置差
    函数输出：
	      无
******************************************************************************/
void ShellInsert(SqList *L, int dk)
{
	 int i,j;

	 //对每个子序列中的元素都采用相同的操作：直接插入排序。每个子序列中的元素
	 //并不是连续的，而是相隔dk个地址空间
	 for(i=dk+1;i<=L->Length;++i){
		 //直接插入排序，只不过应该与待插入元素前dk个位置的元素进行比较
		 if(L->r[i].key<L->r[i-dk].key){
			 L->r[0]=L->r[i];
			 for(j=i-dk;j>0 &&  L->r[0].key<L->r[j].key; j=j-dk)
				 L->r[j+dk]=L->r[j];
			 L->r[j+dk]=L->r[0];
		 }
	 }
  return;
}

/******************************************************************************
    函数：void QuickSort(SqList *L);

    功能：快速排序

    形式参数：
	      L:     指向待排序序列首址
		  
    函数输出：
	      无
******************************************************************************/
void QuickSort(SqList *L)
{
	 QSort(L,1,L->Length);
   return;
}

/******************************************************************************
    函数：void QSort(SqList *L, int low,int high);

    功能：对L序列中的元素（在low到high之间）进行快速排序

    形式参数：
	      L:     指向待排序序列首址
          low:   快速排序的低地址
		  high:  快速排序的高地址
    函数输出：
	      无
******************************************************************************/
void QSort(SqList *L, int low,int high)
{
	int pivotloc;

    //但low地址小于high地址时，进行快速排序
	if(low<high){

		//进行一趟快速排序，并得到枢轴元素当前的位置
		pivotloc=Partion(L,low,high);

		//之前的元素为一个子序列，进行快速排序
		QSort(L,low,pivotloc-1);

		//之后的元素为一个子序列，进行快速排序
		QSort(L,pivotloc+1,high);
	}
   return;
}

/******************************************************************************
    函数：int Partion(SqList *L, int low,int high);

    功能：一趟快速排序

    形式参数：
	      L:     指向待排序序列首址
		  low:   一趟快速排序的低地址
		  high:  一趟快速排序的高地址

    函数输出：
	      无
******************************************************************************/
int Partion(SqList *L, int low,int high)
{
	 int pivotkey;

	 //序列的第一个元素先放在0号存储单元，并不需要马上进行交换
     L->r[0]=L->r[low];

	 //序列的第一个元素为枢轴
	 pivotkey=L->r[low].key;
	 
	 while(low<high){

	     //如果high所指元素大于数组，则继续往前找
		 while(low<high && L->r[high].key>=pivotkey)
			 --high;

		 //反之，则将high所指的元素放在low的位置上
		 L->r[low]=L->r[high];
		 //如果low所指的元素小于枢轴，则继续往后找，直到大于枢轴

		 while(low<high && L->r[low].key<=pivotkey)
			 ++low;

		 //反之，则将low所指元素放在high所指的位置
		 L->r[high]=L->r[low];
	 }

	 //最后一个元素实现枢轴元素放在适当的位置，这样其左边的元素小于枢轴，
	 //其右边的元素大于枢轴
	 L->r[low]=L->r[0];
  return low;
}

/******************************************************************************
    函数：void HeapSort(SqList *H);

    功能：堆排序

    形式参数：
	      H:     指向待排序序列首址
		  
    函数输出：
	      无
******************************************************************************/
void HeapSort(SqList *H)
{
     int i;
	 RedType rc;
	 
	 //不断调整，建立一个大顶堆
	 for(i=H->Length/2;i>0;--i)
		 HeapAdjust(H,i,H->Length);

	 //由于大顶堆的第一个元素为序列中最大的元素，因此交换序列中第一个和序列中
	 //最后一个元素，然后将该序列中除最后一个元素外的其它元素重新调整成一个大
	 //顶的堆，同时将序列元素个数减1,这样不断的循环，便可以将序列编程一个按从
	 //小到大的顺序排列的子序列。
	 for(i=H->Length;i>1;--i){
         //交换子序列第一个和最后一个元素
		 rc=H->r[1];
		 H->r[1]=H->r[i];
         H->r[i]=rc;
		 //重新将其余的元素调整成一个大顶堆
	     HeapAdjust(H,1,i-1);
	 }
   return;
}

/******************************************************************************
    函数：void HeapAdjust(SqList *H,int s, int m);

    功能：将s结点与其左右子树的大者交换，使s结点为左右子树中最大者

    形式参数：
	      H:     指向待排序序列首址
		  s:     待交换的起始结点，调整后该结点为左右子树最大者
		  m:     其左右子树最后一个待调整的结点所在的位置
		  
    函数输出：
	      无
******************************************************************************/
void HeapAdjust(SqList *H,int s, int m)
{
	 RedType rc,rm;
     int  j;
     
	 //将序列的第一个元素暂时保存
	 rc=H->r[s];

	 //从其孩子结点开始，比较其左右孩子，得到其左右孩子的大者
     for(j=2*s;j<=m;j*=2){
		 //如果左孩子小于右孩子，则j+1得到其大者的位置
		 if(j<m && H->r[j].key<H->r[j+1].key)
			 ++j;
		 //如果根结点比左右孩子的大者都大，则不调整
		 if(rc.key>=H->r[j].key)
			 break;
		 //反之，交换根结点与左右孩子的大者
		 rm=H->r[s];
		 H->r[s]=H->r[j];
		 H->r[j]=rm;
		 //然后将该点为起点，继续进行后续的比较，直到比较完所有的结点
		 s=j;
	 }
	 //将初始根结点与左右子树最后的大者交换，使s所指的结点为最大的根结点
	 H->r[s]=rc;

   return;
}

/******************************************************************************
    函数：void MergeSort(SqList *L);

    功能：归并排序

    形式参数：
	      L:     指向待排序序列首址
		  
    函数输出：
	      无
******************************************************************************/
void MergeSort(SqList *L)
{
	 MSort(L->r,L->r,1,L->Length);
   return;
}

/******************************************************************************
    函数：void MSort(RedType *SR, RedType *TR1, int s,int t);

    功能：实现从s位置开始到t位置为止的元素进行归并排序

    形式参数：
	      SR:    存放待排序序列的关键字
		  TR1:   存放归并后的结果
		  s:     待排序序列的起始位置
		  t:     待排序序列的终止位置
		  
    函数输出：
	      无
******************************************************************************/
void MSort(RedType *SR, RedType *TR1, int s,int t)
{

	 RedType *TR2;
	 int  m;

	 //分配临时存储空间
	 TR2=(RedType*)malloc(sizeof(RedType)*(t+1));

	 //如果起始位置和终止位置相同，则直接将待归并序列保存到结果中
	 if(s==t)
		 TR1[s]=SR[s];
	 //递归地将原序列分成两个部分，然后再归并成一个序列
	 else{
		 m=(s+t)/2;
		 MSort(SR,TR2,s,m);
		 MSort(SR,TR2,m+1,t);
		 Merge(TR2,TR1,s,m,t);
	 }

     free(TR2);
   return;
}

/******************************************************************************
    函数：void Merge(RedType *SR, RedType *TR, int i,int m,int n);

    功能： 将有序地SR[i...m]和SR[m+1...n]归并为有序地TR[i...n]

    形式参数：
	      
	      SR:    存放待排序序列的关键字
		  TR:    存放归并后的结果
		  i:     第一个序列的起始地址
		  m:     第一个子序列最后一个元素的地址
		  n:     第二个子序列最后一个元素的地址
		  
    函数输出：
	      无
******************************************************************************/
void Merge(RedType *SR, RedType *TR, int i,int m,int n)
{
      int j,l,k;

      //将有序地SR[i...m]和SR[m+1...n]归并为有序地TR[i...n]
	  for(j=m+1,k=i;i<=m&&j<=n;++k){
		  //如果第一个序列的第i个关键字小于第二个序列的第j个关键字，则将
		  //第i个关键字送到TR中，反之，将第j个关键字送到TR中
		  if(SR[i].key<=SR[j].key)
			  TR[k]=SR[i++];
		  else
			  TR[k]=SR[j++];
	  }

	  //将剩余的关键字（包括前面部分和后面部分）送到TR中
	  if(i<=m){
		  for(l=k;i<=m;l++,i++)
			  TR[l]=SR[i];
	  }
	  if(j<=n){
		  for(l=k;j<=n;l++,j++)
			  TR[l]=SR[j];
	  }

  return;
}