C语言数据结构与算法之排序总结(二) C语言数据结构与算法之排序总

一、前言
二、选择类排序

1.简单选择排序
2.树形选择排序
3.堆选择排序

三、归并排序

四、分配类排序

1.多关键字排序
2.链式基数排序

五、总结归纳

一、前言之前的排序总结（一）对插入类和交换类排序作了比较详细的总结，对于直接插入、希尔排序、冒泡排序、快速排序要求熟练掌握
这篇排序全面总结(二)主要介绍选择类排序中的简单、树形和堆排序，归并排序、分配类排序的基数排序

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

1.简单选择排序
动态演示：

算法讲解：

首先通过n-1次比较，从n个记录中找出最小值，将它与第一个元素交换
再通过n-2次比较，从剩余的n-1个记录中找出次小的值，将它与第二个记录交换
重复上述操作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.树形选择排序
静态演示：

文章图片

算法讲解：

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

特点：
算法不作要求
稳定排序, 增加额外的存储空间
时间复杂度O（nlogn）,空间复杂度O(n-1)

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); }

调整堆：

voidsift(RecordTyper[],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= r[j].key) finished=TRUE; /*筛选完毕*/ else {r[i] = r[j]; i=j; j=2*i; }/* 继续筛选 */ }r[i] =t; /* r[k]填入到恰当的位置 */ }

堆排序：

voidHeapSort(RecordTyper[],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 ( RecordTyper[], int n) /* 对记录数组r[1..n]做归并排序 */ { MSort ( r, 1, n, r); }voidMSort(RecordTyper1[],intlow,inthigh,RecordTyper3[])/* r1[low..high]经过排序后放在r3[low..high]中，r2[low..high]为辅助空间 */ { int mid; RecordTyper2[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.多关键字排序