堆排序也是选择排序的一种，其特点是，在以后各趟的“选择”中利用在第一趟选择中已经得到的关键字比较的结果。
堆的定义:
堆是满足下列性质的数列{r1, r2, …，rn}：
或
若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左/右子树不空时，根结点的值小于(或大于)左/右子树根结点的值。
由此，若上述数列是堆，则r1必是数列中的最小值或最大值，分别称作小顶堆或大顶堆。
堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。具体作法是：先建一个“大顶堆”，即先选得一个关键字为最大的记录，然后与序列中最后一个记录交换，之后继续对序列中前n-1记录进行“筛选”，重新将它调整为一个“大顶堆”，再将堆顶记录和第n-1个记录交换，如此反复直至排序结束。
所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树为堆。
堆排序的算法如下所示：
template
void HeapSort ( Elem R[], int n ) {
// 对记录序列R[1..n]进行堆排序。
for ( i=n/2; i>0; --i )
// 把R[1..n]建成大顶堆
HeapAdjust ( R, i, n );
for ( i=n; i>1; --i ) {
R[1]←→R;
// 将堆顶记录和当前未经排序子序列
// R[1..i]中最后一个记录相互交换
HeapAdjust(R, 1, i-1);
// 将R[1..i-1] 重新调整为大顶堆
}
} // HeapSort
其中筛选的算法如下所示。为将R[s..m]调整为“大顶堆”，算法中“筛选”应沿关键字较大的孩子结点向下进行。
Template
void HeapAdjust (Elem R[], int s, int m) {
// 已知R[s..m]中记录的关键字除R[s].key之
// 外均满足堆的定义，本函数调整R[s] 的关
// 键字，使R[s..m]成为一个大顶堆（对其中
// 记录的关键字而言）
rc = R[s];
for ( j=2*s; j<=m; j*=2 ) {// 沿key较大的孩子结点向下筛选
if ( j
if ( rc.key >= R[j].key ) break; // rc应插入在位置s上
R[s] = R[j]; s = j;
}
R[s] = rc; // 插入
} // HeapAdjust
堆排序的时间复杂度分析：
1. 对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1);
2．对n个关键字，建成深度为h(=?log2n?+1)的堆，所需进行的关键字比较的次数至多为4n;
3. 调整“堆顶”n-1次，总共进行的关键字比较的次数不超过
2(log2(n-1)?+ ?log2(n-2)?+ …+log22)<2n(?log2n?)
因此，堆排序的时间复杂度为O(nlogn)
四．归并排序：是通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度;归并排序的基本思想是：将两个或两个以上的有序子序列“归并”为一个有序序列。
在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列 归并为一个有序序列。
“归并”算法描述如下：
template
void Merge (Elem SR[], Elem TR[], int i, int m, int n) {
// 将有序的SR[i..m]和SR[m+1..n]归并为
// 有序的TR[i..n]
for (j=m+1, k=i; i<=m && j<=n; ++k)
{ // 将SR中记录由小到大地并入TR
if (SR.key<=SR[j].key) TR[k] = SR[i++];
else TR[k] = SR[j++];
}
if (i<=m) TR[k..n] = SR[i..m];
// 将剩余的SR[i..m]复制到TR
if (j<=n) TR[k..n] = SR[j..n];
// 将剩余的SR[j..n]复制到TR
} // Merge
归并排序的算法可以有两种形式：递归的和递推的，它是由两种不同的程序设计思想得出的。在此，只讨论递归形式的算法。
这是一种自顶向下的分析方法：
如果记录无序序列R[s..t]的两部分R[s..?(s+t)/2?]和R[?(s+t)/2+1..t?分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列，由此，应该先分别对这两部分进行2-路归并排序。
template
void Msort ( Elem SR[], Elem TR1[], int s, int t ) {
// 将SR[s..t]进行2-路归并排序为TR1[s..t]。
if (s==t) TR1[s] = SR[s];
else {
m = (s+t)/2;
// 将SR[s..t]平分为SR[s..m]和SR[m+1..t]
Msort (SR, TR2, s, m);
// 递归地将SR[s..m]归并为有序的TR2[s..m]
Msort (SR, TR2, m+1, t);
//递归地SR[m+1..t]归并为有序的TR2[m+1..t]
Merge (TR2, TR1, s, m, t);
// 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
}
} // MSort
template
void MergeSort (Elem R[]) {
// 对记录序列R[1..n]作2-路归并排序。
MSort(R, R, 1, n);
} // MergeSort
容易看出，对n个记录进行归并排序的时间复杂度为Ο(nlogn)。即：每一趟归并的时间复杂度为O(n)，总共需进行logn趟。
五．基数排序：借助“多关键字排序”的思想来实现“单关键字排序”的算法。
[I]多关键字的排序
假设有n个记录……的序列
{ R1, R2, …，Rn}
每个记录Ri中含有d个关键字(Ki0, Ki1, …,Kid-1),则称上述记录序列对关键字(Ki0, Ki1, …,Kid-1)有序是指：对于序列中任意两个记录Ri和Rj(1≤i
(Ki0, Ki1, …,Kid-1)< (Kj0, Kj1, …,Kjd-1)
其中K0被称为“最主”位关键字，Kd-1被称为 “最次”位关键字。
实现多关键字排序通常有两种作法:
最高位优先MSD法：先对K0进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别对K1进行排序，…，依次类推，直至最后对最次位关键字排序完成为止。
最低位优先LSD法：先对Kd-1进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字K0排序完成为止。排序过程中不需要根据“前一个”关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。
例如:学生记录含三个关键字:系别、班号和班内的序列号，其中以系别为最主位关键字。LSD的排序过程如下:
[II]链式基数排序
假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。
对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。
例如：对下列这组关键字
{209, 386, 768, 185, 247, 606, 230, 834, 539 }
首先按其“个位数”取值分别为0, 1, …，9“分配”成10组，之后按从0至9的顺序将它们“收集”在一起;然后按其“十位数” 取值分别为0, 1, …，9“分配”成10组，之后再按从0至9的顺序将它们“收集”在一起;最后按其“百位数”重复一遍上述操作，便可得到这组关键字的有序序列。
在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：
１． 待排序记录以指针相链，构成一个链表；
２．“分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的“关键字位”相同；
３．“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表;
４．对每个关键字位均重复2)和3)两步。
例如：
p→369→367→167→239→237→138→230→139
第一次分配得到
f[0]→230←r[0]
f[7]→367→167→237←r[7]
f[8]→138←r[8]
f[9]→369→239→139←r[9]
第一次收集得到
p→230→367→167→237→138→368→239→139
第二次分配得到
f[3]→230→237→138→239→139←r[3]
f[6]→367→167→368←r[6]
第二次收集得到
p→230→237→138→239→139→367→167→368
第三次分配得到
f[1]→138→139→167←r[1]
f[2]→230→237→239←r[2]
f[3]→367→368←r[3]
第三次收集之后便得到记录的有序序列
p→138→139→167→230→237→239→367→368
我们在技术排序中需要注意的是：
１．“分配”和“收集”的实际操作仅为修改链表中的指针和设置队列的头、尾指针；
２．为查找使用，该链表尚需应用算法Arrange将它调整为有序表。
基数排序的时间复杂度为O(d(n+rd))。
其中，分配为O(n);收集为O(rd)(rd为“基”),d为“分配-收集”的趟数。
下面我们比较一下上面谈到的各种内部排序方法
首先，从时间性能上说：
1. 按平均的时间性能来分，有三类排序方法：
时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；
时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此；
时间复杂度为O(n)的排序方法只有，基数排序。
2. 当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。
3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
其次，从空间性能上说：
指的是排序过程中所需的辅助空间大小。
1. 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；
2. 快速排序为O(logn)，为栈所需的辅助空间;
3. 归并排序所需辅助空间最多，其空间复杂度为O(n);
4. 链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)。
再次，从排序方法的稳定性能上说：
稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。对于不稳定的排序方法，只要能举出一个实例说明即可。我们需要指出的是：快速排序和堆排序是不稳定的排序方法。
我们再谈谈关于“排序方法的时间复杂度的下限”
这里讨论的各种排序方法，除基数排序外，其它方法都是基于“比较关键字”进行排序的排序方法，可以证明，这类排序法可能达到的最快的时间复杂度为O(nlogn)。(基数排序不是基于“比较关键字”的排序方法,所以它不受这个限制)。可以用一棵判定树来描述这类基于“比较关键字”进行排序的排序方法。
例如，对三个关键字进行排序的判定树如下：
K1
K1
K2< K3 K2
K3
描述排序的判定树有两个特点：
１．树上的每一次“比较”都是必要的;
２． 树上的叶子结点包含所有可能情况。
则由上图所示“判定树的深度为4”可以推出“至多进行三次比较”即可完成对三个关键字的排序。反过来说，由此判定树可见，考虑最坏情况，“至少要进行三次比较”才能完成对三个关键字的排序。对三个关键字进行排序的判定树深度是唯一的。即无论按什么先后顺序去进行比较，所得判定树的深度都是3。当关键字的个数超过3之后，不同的排序方法其判定树的深度不同。例如，对4个关键字进行排序时，直接插入的判定树的深度为6, 而折半插入的判定树的深度为5。
可以证明，对4个关键字进行排序，至少需进行5次比较。因为，4个关键字排序的结果有4!=24种可能，即排序的判定树上必须有24个叶子结点，其深度的最小值为6。
一般情况下，对n个关键字进行排序，可能得到的结果有n! 种，由于含n! 个叶子结点的二叉树的深度不小于?log2(n!)? +1, 则对n个关键字进行排序的比较次数至少是?log2(n!)? 。利用斯蒂林近似公式?log2(n!)? ? nlog2n
所以，基于“比较关键字”进行排序的排序方法，可能达到的最快的时间复杂度为O(nlogn)。
下面我们再来谈谈外部排序：
常见的外部排序有：
磁盘排序和磁带排序，之所以这么分是因为外排序不但与排序的算法有关，还与外存设备的特征有关。结合外存设备特征，大体上可分为顺序存取（如磁带）和直接存取（如磁盘）两大类。磁带排序时间主要取决于对带的读写。（这里只是交代一下，实际上正如大家知道的，基本上现在已经淘汰了磁带存储的方式）需要指出的是外部排序的这两种方式的工作过程是一致的，外部排序的基本过程由相对独立的两个步骤组成：
１．按可用内存大小，利用内部排序的方法，构造若干(记录的)有序子序列，通常称外存中这些记录有序子序列为“归并段”;
２．通过“归并”，逐步扩大(记录的)有序子序列的长度，直至外存中整个记录序列按关键字有序为止。
例如：假设有一个含10,000个记录的磁盘文件，而当前所用的计算机一次只能对1,000个记录进行内部排序，则首先利用内部排序的方法得到10个初始归并段，然后进行逐趟归并。
假设进行2?路归并(即两两归并)，则
第一趟由10个归并段得到5个归并段;
第二趟由 5 个归并段得到3个归并段;
第三趟由 3 个归并段得到2个归并段;
最后一趟归并得到整个记录的有序序列。
我们来分析上述外排过程中访问外存(对外存进行读/写)的次数：假设“数据块”的大小为200，即每一次访问外存可以读/写200个记录。则对于10,000个记录，处理一遍需访问外存100次(读和写各50次)。
由此，对上述例子而言，
1) 求得10个初始归并段需访问外存100次;
2) 每进行一趟归并需访问外存100次;
3) 总计访问外存 100 + 4 ? 100 = 500次。
外排总的时间还应包括内部排序所需时间和逐趟归并时进行内部归并的时间，显然，除去内部排序的因素外，外部排序的时间取决于逐趟归并所需进行的“趟数”。
例如，若对上述例子采用5?路归并，则只需进行2趟归并，总的访问外存的次数将压缩到 100 + 2 ? 100 = 300 次
一般情况下，假设待排记录序列含m个初始归并段，外排时采用k?路归并，则归并趟数为 ?logkm?，显然，随之k的增大归并的趟数将减少，因此对外排而言，通常采用多路归并。k的大小可选，但需综合考虑各种因素。
上面谈的都是假设在单处理机上完成的工作，下面将谈谈并行排序：
并行排序：是指利用多台处理机（并行机）进行的排序，其目的主要是为了提高速度。并行排序算法虽然和前面谈到的单处理机上的串行排序算法有不少相似之处，但不能认为它只是它是串行算法的简单推广和扩充。它的最大特点之一就是他和并行计算机的体系结构密切相关，不同体系结构导致不同加速和不同设计风格的并行排序算法。
图与网络优化算法：
组合算法中内容最丰富的部分就是图与网络优化算法。图论中的计算问题包括图的搜索、路径问题、连通性问题、可平面性检验、着色问题、网络优化等。图论中的著名算法有：求最小生成树的Kruskal算法、求最短路径的Dijkstra算法和Floyd算法、求二部图最大匹配（指派问题）的匈牙利算法、求一般图最大匹配的Edmonds“花”算法、求网络最大流和最小割的算法等。
求最小生成树的Kruskal算法
由于这个是大家都熟悉的，我只简单的说说：为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能地小。Kruskal算法的做法就是：先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。算法如下:
构造非连通图 ST=( V,{ } );
k = i = 0;
while (k
++i;
从边集 E 中选取第i条权值最小的边(u,v);
若(u,v)加入ST后不使ST中产生回路，
则 输出边(u,v);
k++;
}
