c/c++语言开发共享C语言数据结构与算法之排序总结(二)

目录

• 一、前言
• 二、选择类排序
• 1.简单选择排序
• 2.树形选择排序
• 3.堆选择排序
• 三、归并排序
• 四、分配类排序
• 1.多关键字排序
• 2.链式基数排序
• 五、总结归纳

  void selectsort(recordtype r[], int length)  /*对记录数组r做简单选择排序，length为数组的长度*/  {  	int i,j,k;	int n;	recordtype x;    n=length;  	for ( i=1 ; i<= n-1; ++i)    	{  		k=i;  		for (j=i+1 ; j<= n ; ++j)   			if (r[j].key < r[k].key ) k=j;  		if ( k!=i)   		 {   		     x= r[i];   r[i]= r[k];   r[k]=x;  		}  	}	  } /* selectsort  */ 

  void crt_heap(recordtype r[], int length )  /*对记录数组r建堆，length为数组的长度*/  {  	int i,n;      n= length;  	for ( i=n/2; i >= 1; --i) /* 自第[n/2]个记录开始进行筛选建堆 */   		sift(r,i,n);  }

  void  sift(recordtype  r[],  int k, int m)  /* 假设ｒ[k..m]是以ｒ[k]为根的完全二叉树，且分别以ｒ[2k]和ｒ[2k+1]为根的左、右子树为大根堆，调整r[k]，使整个序列r[k..m]满足堆的性质 */  {	recordtype t;	int i,j;	int x;	int finished;  	t= r[k];          /* 暂存"根"记录r[k] */ 	       x=r[k].key;	i=k;	j=2*i;  	finished=false;  	while( j<=m && !finished  )   		{       		     if (j<m  && r[j].key< r[j+1].key )  j=j+1;   /* 若存在右子树，                                                       且右子树 根的关键字大，则沿右分支"筛选" */  		     if ( x>= r[j].key)	finished=true;            /*  筛选完毕  */   		     else   		     {   r[i] = r[j];  i=j;  j=2*i;	}    /* 继续筛选 */   		}  		r[i] =t;          /* r[k]填入到恰当的位置 */   } 

  void  heapsort(recordtype  r[],int length)  /* 对r[1..n]进行堆排序，执行本算法后，r中记录按关键字由大到小有序排列 */   {  	int i,n;	recordtype b;  	crt_heap(r, length);	n= length;  	for (  i=n ; i>= 2; --i)   	{  		b=r[1];     /* 将堆顶记录和堆中的最后一个记录互换 */   		r[1]= r[i];  		r[i]=b;   		sift(r,1,i-1);  /* 进行调整，使r[1..i-1]变成堆 */   	}  } /* heapsort */ 

  void mergesort ( recordtype  r[], int n) /* 对记录数组r[1..n]做归并排序 */   {  	msort ( r, 1, n, r);  }  void   msort(recordtype  r1[],  int  low,  int  high,  recordtype  r3[])  /* r1[low..high]经过排序后放在r3[low..high]中，r2[low..high]为辅助空间 */   {  	int mid;   recordtype  r2[20];  	if (low==high)   r3[low]=r1[low];  	else  	{  		mid=(low+high)/2;          msort(r1,low, mid, r2);          msort(r1,mid+1,high, r2);          merge (r2,low,mid,high, r3);       }  } /*   msort  */