亲宝软件园·资讯

展开

C语言 数据结构 排序

知心宝贝 人气:0

一、前言

之前的排序总结(一)对插入类和交换类排序作了比较详细的总结,对于直接插入、希尔排序、冒泡排序、快速排序要求熟练掌握

这篇排序全面总结(二)主要介绍选择类排序中的简单、树形和堆排序,归并排序、分配类排序的基数排序

二、选择类排序

选择类:每次从待排序的无序序列中,选择一个最大或最小的数字,放到前面,数据元素为空时排序结束

1.简单选择排序

动态演示:

算法讲解:

  1. 首先通过n-1次比较,从n个记录中找出最小值,将它与第一个元素交换
  2. 再通过n-2次比较,从剩余的n-1个记录中找出次小的值,将它与第二个记录交换
  3. 重复上述操作n-1,排序完成

代码:

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  */ 

特点: 

不稳定排序

时间复杂度O(n*n), 空间复杂度O(1)

2.树形选择排序

静态演示:

算法讲解:

  1. 最下面一行21 25 49 25 16 08 63是给定需要从小到大排序的数字
  2. 相邻的两个选出一个最小的向上移一层,只有一个的补一个值无穷大的数
  3. 倒数第二层再次两两组合,直到最顶端
  4. 此时,最顶端08就是值最小的数,输出08,把所有08至为无穷大
  5. 再次选出一个最小值,以此类推

特点: 

算法不作要求

稳定排序, 增加额外的存储空间

时间复杂度O(nlogn),空间复杂度O(n-1)

3.堆选择排序

动态演示:

算法讲解:

  1. 根结点值最大的叫大顶堆,根结点值最小的叫小顶堆,上图就是一个构造大顶堆的图
  2. 从最后一层开始,如果孩子结点的值比父亲结点大,那么就交换位置
  3. 一层层向上推,直到根结点值最大

建立初始堆:

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)
/* 假设r[k..m]是以r[k]为根的完全二叉树,且分别以r[2k]和r[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 */ 

特点: 

堆选择是树形的改进,空间占用较小

不稳定排序,适合n值较大的排序

时间复杂度O(n*logn),空间复杂度O(1)

三、归并排序

法一:

将整体数字一分为二,逐层细分

细分完成后,每一块进行排序,直到整体有序

法二:

将一串序列,相邻的两个归并到一起排序,再次把相邻两个有序的归并块再次排序,直到最后有序(优先推荐这种算法)

代码:

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  */ 

特点: 

稳定排序

时间复杂度O(nlogn),空间复杂度O(n)

附加空间比较大,很少用于内部排序,主要是外部排序

四、分配类排序

1.多关键字排序

高位优先:按照花色大小分成四类,在每一类中按照面值进行排序

低位优先:按照面值大小分成13类,将相同面值的不同花色进行排序

2.链式基数排序

算法讲解:

  1. 对于上面的9个三位数,第一步我们按照个位数从小到大排序
  2. 接着第一步的结果,按照十位数从小到达排序
  3. 最后借助第二步的结果,按照百位数从小到大排序
  4. 同样的,对于4位 5 位方法一样

特点:

时间复杂度O(d*n),d是关键字数,n是记录数

稳定的排序

空间复杂度=2个队列指针+n个指针域

五、总结归纳

加载全部内容

相关教程
猜你喜欢
用户评论