5、堆排序(HeapSort)
在接触“堆排序”前，先回顾一下数据结构C#版笔记--树与二叉树 ，其中提到了“完全二叉树”有一些重要的数学特性：
上图就是一颗完全二叉树，如果每个节点按从上到下，从左至右标上序号，则可以用数组来实现顺性存储，同时其序号：
1、如果i>1，则序号为i的父结节序号为i/2(这里/指整除) 言外之意：整个数组前一半都是父节点，后一半则是叶节点
2、如果2*i<=n（这里n为整颗树的节点总数），则序号为i的左子节点序号为2*i
3、如果2*i +1 <=n，则序号为i的右子节点序号为2*i + 1
好了，再来看看"堆(Heap)"是个神马玩意儿？
其实，堆就是一颗完全二叉树，由上面的知识点回顾可以知道，任意给定一个数组，我们就能将它构造成一颗完全二叉树，也就是创建一个“堆”--ps：还好业内标准称它为一堆，而不是一坨 ：）
其中，堆又可以分为最大堆与最小堆，下图就是一个最大堆：
简言之：每个(父)节点的值，都比其子节点值大，这样的堆就称为最大堆；反过来类推，如果每个（父）节点的值，都比其子节点小，就叫最小堆。
下面该"堆排序"(HeapSort)登场了，其思路为：
1、先将给定待排序的数组通过一定处理，形成一个“最大堆”
2、然后将根节点(root)与最后一个序号的节点(lastNode)对换，这样值最大的根节点，就“沉”到所有节点最后了(也就是垫底了)，下轮处理就不用理会它了.
3、因为第2步的操作，剩下的这些节点肯定已经不满足最大堆的定义了(因为把小值的末节点换成根节点了，它的子节点中肯定会有值比它大的)，然后再类似第1步的处理，把这些剩下的节点重新排成“最大堆”
4、重复第2步的操作，将“新最大堆的根节点”与“新最大堆的末结点”(其实就是整个数组的倒数第二个节点，因为在第一轮处理中，最大值的节点已经沉到最后了，所以新最大堆的最末节点就是整个数组的倒数第二个节点)对换，这样第二大的元素也沉到适当的位置了，以后就不用理它了，然后继续把剩下的节点，重组成最大堆
5、反复以上过程，直到最后剩下的节点只剩一个为止（即没办法再继续重组成最大堆），这时排序结束，最后剩下的节点，肯定就是值最小的
假设给定数组new int[] {1,3,5,6,4,2}，要求用“堆排序算法”从小到大排序，上面的算法描述图解为：
理解以上思路后，堆排序就拆分成了二个问题：
A、如何将数组指定范围的N个元素创建一个"最大堆"？
B、如何用一定的算法，反复调用A中的"最大堆创建"方法，以处理剩下的节点，直到最终只剩一个元素为止
创建最大堆的算法，完全依赖于完全二叉树的数学特性，代码如下：
/// <summary>
/// 创建最大堆
/// </summary>
/// <param name="arr">待处理的数组</param>
/// <param name="low">指定连续待处理元素范围的下标下限</param>
/// <param name="high">指定连续待处理元素范围的下标上限</param>
static void CreateMaxHeap(int[] arr, int low, int high)
{
if ((low < high) && (high <= arr.Length - 1))
{
int j = 0, k = 0, t = 0;
//根据完全二叉树特性，前一半元素都是父节点，所以只需要遍历前一半即可
for (int i = high / 2; i >= low; --i)
{
k = i;
t = arr[i];//暂存当前节点值
j = 2 * i + 1;//计算左节点下标(注意：数组下标是从0开始的，而完全二叉树的序号是从1开始的，所以这里的2*i+1是左子节点，而非右子节点！)
while (j <= high) //如果左节点存在
{
//如果右节点也存在，且右节点更大
if ((j < high) && (j + 1 <= high) && (arr[j] < arr[j + 1]))
{
++j;//将j值调整到右节点的序号，即经过该if判断后，j对应的元素就是i元素的左、右子节点中值最大的
}
//如果本身节点比子节点小
if (t < arr[j])
{
arr[k] = arr[j];//将自己节点的值，更新为左右子节点中最大的值
//然后保存左右子节点中最大元素的下标(因为实际上要做的是将最大子节点与自身进行值交换，
//上一步只完成了交换值的一部分，后面还会继续处理才能完成整个交换)
k = j;
j = 2 * k + 1;//交换后，j元素就是父节点了，然后重新以j元素为父节点，继续考量其"左子节点"，准备进入新一轮while循环
}
else //如果本身已经是最大值了，则说明元素i所对应的子树，已经是最大堆，则直接跳出循环
{
break;
}
}
//接上面的交换值操作，将最大子节点的元素值替换为t(因为最近的一次if语句中，k=j 了，
//所以这里的arr[k]其实就是arr[j]=t，即完成了值交换的最后一步，
//当然如果最近一次的if语句为false,根本没进入，则这时的k仍然是i，维持原值而已)
arr[k] = t;
}
}
}
反复调用该算法排序的代码：
/// <summary>
/// 堆排序
/// </summary>
/// <param name="arr"></param>
static void HeapSort(int[] arr)
{
int tmp = 0;
//初始时，将整个数组排列成"初始最大堆"
CreateMaxHeap(arr, 0, arr.Length - 1);
for (int i = arr.Length - 1; i > 0; --i)
{
//将根节点与最末结点对换
tmp = arr[0];
arr[0] = arr[i];
arr[i] = tmp;
//去掉沉底的元素，剩下的元素重新排列成“最大堆”
CreateMaxHeap(arr, 0, i - 1);
}
}
点评：这是一种思维方式很独特的排序方式，时间复杂度跟快速排序类似，也是跟二叉树有关，为O(Nlog2N)，同样它也是一种不稳定的排序。
6、归并排序算法（MergeSort）
思路：将数组中的每个元素看作一个小序列，然后二二合并成一个有序的新序列(这样序列个数从N变成了N/2，但是每个小序列的长度从1变成2)，然后继续将这些新序列二二合并，得到N/4个序列(每个序列的长度从2变成4)，如此反复，最终得到一个全部排列好的完整序列。这也是算法中"分治法"的经典案例之一，即分而治之。
这里反复要用到将二个序列合并为新序列的处理，封装成以下方法 ：
/// <summary>
/// 归并处理
/// </summary>
/// <param name="arr">需要归并处理的数组</param>
/// <param name="len">每段小序列的长度</param>
static void Merge(int[] arr, int len)
{
int m = 0; //临时顺序表的起始位置
int low1 = 0; //第1个有序表的起始位置
int high1; //第1个有序表的结束位置
int low2; //第2个有序表的起始位置
int high2; //第2个有序表的结束位置
int i = 0;
int j = 0;
//临时表，用于临时将两个有序表合并为一个有序表
int[] tmp = new int[arr.Length];
//归并处理
while ((low1 + len) < arr.Length)
{
low2 = low1 + len; //第2个有序表的起始位置
high1 = low2 - 1; //第1个有序表的结束位置
//第2个有序表的结束位置
high2 = ( (low2 + len - 1) < arr.Length) ? low2 + len - 1 : arr.Length - 1;
i = low1;
j = low2;
//如果二个有序表都还没整完
while ((i <= high1) && (j <= high2))
{
if (arr[i] <= arr[j])//如果 第1个有序表的元素小于第2个有序表的对应元素，则直接复制第1个有序表的元素到临时表
{
tmp[m++] = arr[i++];
}
else//否则，复制第2个有序表的元素到临时表
{
tmp[m++] = arr[j++];
}
}
//经过上面的处理后，如果第1个有序表还有元素
while (i <= high1)
{
tmp[m++] = arr[i++];
}
//经过上面的处理后，如果第2个有序表还有元素
while (j <= high2)
{
tmp[m++] = arr[j++];
}
low1 = high2 + 1;//将low1"指针"指到“处理完的2个有序表”之后，以方便下面将剩余未处理完的元素复制到临时表
}
i = low1;
//将尚未处理到的元素复制到临时表
while (i < arr.Length)
{
tmp[m++] = arr[i++];
}
//将临时表的元素复制到原数组
for (i = 0; i < arr.Length; ++i)
{
arr[i] = tmp[i];
}
}
排序处理：
/// <summary>
/// 归并排序
/// </summary>
/// <param name="arr"></param>
static void MergeSort(int[] arr)
{
int k = 1; //归并增量
while (k < arr.Length)
{
Merge(arr, k);
k *= 2;
}
}
}
点评：俩俩合并，又是跟2有关的，哈哈，计算机领域真的很2啊！所以其时间复杂度又是O(Nlog2N），但是该算法需要很多的临时数组，所以其空间复杂度较其它算法都要大一些为O(N)，此外它是稳定的排序方法。
排序方法小结：(原书的小结还算不错，就懒得自己再写了，直接从原电子书上copy过来记录下)
排序在计算机程序设计中非常重要，上面介绍的各种排序方法各有优缺点，适用的场合也各不相同。
在选择排序方法时应考虑的因素有：
（1）待排序记录的数目 n 的大小；
（2）记录本身除关键码外的其它信息量的大小；
（3）关键码(即元素值)的情况；
（4）对排序稳定性的要求；
（5）语言工具的条件，辅助空间的大小等。
综合考虑以上因素，可以得出如下结论：
（1）若排序记录的数目 n 较小（如 n≤50）时，可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多，因而当记录本身信息量较大时，用简单选择排序比较好。
（2）若记录的初始状态已经按关键码基本有序，可采用直接插入排序或冒泡排序。
（3）若排序记录的数目n较大，则可采用时间复杂度为O（nlog2n）的排序方法（如快速排序、堆排序或归并排序等）。
快速排序的平均性能最好，在待排序序列已经按关键码随机分布时，快速排序最适合。快速排序在最坏情况下的时间复杂度是O（n2），而堆排序在最坏情况下的时间复杂度不会发生变化，并且所需的辅助空间少于快速排序。但这两种排序方法都是不稳定的排序，若需要稳定的排序方法，则可采用归并排序。
（4）前面讨论的排序算法，都是采用顺序存储结构。在待排序的记录非常多时，为避免花大量的时间进行记录的移动，可以采用链式存储结构。直接插入排序和归并排序都可以非常容易地在链表上实现，但快速排序和堆排序却很难在链表上实现。此时，可以提取关键码建立索引表，然后对索引表进行排序。也可以引入一个整形数组 t[n]作为辅助表，排序前令t[i]=i，1≤i≤n。若排序算法中要求交换记录 R[i]和 R[j]，则只须交换 t[i]和 t[j]即可。排序结束后，数组 t[n]就存放了记录之间的顺序关系
