堆排序
———————————————————引言——————————————————
由 树形选择排序 优化而来
锦标赛排序：
锦标赛排序，也称为树形选择排序（Tree Selection Sort），是一种按照锦标赛的思想进行选择排序的方法。
首先对n个记录进行两两比较，然后优胜者之间再进行两两比较，如此重复，直至选出最小关键字的记录为止。这个过程可以用一棵有n个叶子结点的完全二 叉树表示。根节点中的关键字即为叶子结点中的最小关键字。在输出最小关键字之后，根据关系的可传递性，欲选出次小关键字，仅需将叶子结点中的最小关键字改 为“最大值”，如∞，然后从该叶子结点开始，和其左（右）兄弟的关键字进行比较，修改从叶子结点到根的路径上各结点的关键字，则根结点的关键字即为次小关 键字。
这种算法的缺点在于：辅助存储空间较多、最大值进行多余的比较。
为了弥补这些缺点，1964年，堆排序诞生。 此段摘自： http://roclinux.cn/?p=675
树形选择排序图示：
------------图 《数据结构》（严蔚敏）
————————————————————————引言end—————————————————————————————
第一部分：概念
1.堆
堆的定义如下：n个元素的序列{k1 ,k2 ,,...,kn }当且仅当满足下关系时，称之为堆。
ki <= k2i ki <= k2i+1 （小顶堆） 或
ki >= k2i ki >= k2i+1 (大顶堆)
（i = 1,2,...,[n/2]）
若将和此序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。
由此，若序列{k1 ,k2 ,,...,kn }是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
例如，下列两个序列为堆，对应的完全二叉树如图
2.堆排序
以图（b）为例：
若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素中的次小值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。
—————————————————————————————————————————————————————————
第二部分 一点疑惑
a. 概念
刚 研究 堆排序 的时候，将【完全二叉树，堆】的概念无法联系到排序中，很混乱。
堆的定义是应堆排序而生的，堆的表现形式即为完全二叉树；
好了，再来看看"堆(Heap)"是个神马玩意儿？
其实，堆就是一颗完全二叉树，任意给定一个数组，我们就能将它构造成一颗完全二叉树，也就是创建一个“堆”
--ps：还好业内标准称它为一堆，而不是一坨 ：）
-----------http://www.cnblogs.com/yjmyzz/archive/2010/12/21/1913102.html
过程是这样的：（以对序列倒序 排序为例）
1. 待排序的序列 {40,55,49,73,12,27,98,81,64,36}（一维数组）
2. 构造大顶堆（大顶堆，完全二叉树）
3. 由上图，得到新序列{98,81,49,73,36,27,40,55,64,12}；（将大顶堆还原为一维数组）
4. 交换 98 和 12，得到新序列{12,81,49,73,36,27,40,55,64,98}；（一维数组）
5. 对 去掉 98的 新序列{12,81,49,73,36,27,40,55,64}构造大顶堆 即重复2；（新一维数组继续构造大顶堆）
整个过程为下图：
b. 筛选
图中 “筛选”的过程，即是重新构造大顶堆的过程。（我们应将“筛选” 单独出来一个算法）
第三部分：算法和源代码
算法如下：
实现源 代码如下：
void heap_adjust(int *arr, int s, int m) { int i; arr[0]=arr[s]; for(i=2*s;i<=m;i*=2){ if((i<m)&&(arr[i]<arr[i+1]))i++; if(arr[0]>=arr[i])break; arr[s]=arr[i]; s=i; } arr[s]=arr[0]; } void heap_sort(int *arr,int arrsize) { int i,tmp; for(i=arrsize/2;i>0;i--) heap_adjust(arr,i,arrsize); for(i=arrsize;i>1;i--){ tmp=arr[1]; arr[1]=arr[i]; arr[i]=tmp; heap_adjust(arr,1,i-1); } } int _tmain(int argc, _TCHAR* argv[]) { printf("Quick Sort:/n"); int arr[10]={0,4,2,5,1,8,7,9}; int arrsize=7; heap_sort(arr,arrsize); int i; printf("Sorted array: "); for(i=1;i<=arrsize;i++){ printf("%d ",arr[i]); } printf("/n"); return 0; }
第四部分 各种网摘总结
1.这是一种思维方式很独特的排序方式，时间复杂度跟快速排序类似，也是跟二叉树有关，为O(Nlog2N)，同样它也是一种不稳定 的排序。
2.
csdn 有篇帖子是说 " 从 5000 个数中找出 10 个最大的用哪种排序最快 ", 答案是堆排序 . 我看网上说 :" 直接选择排序中，为了从 R[1..n] 中选出关键字最小的记录，必须进行 n-1 次比较，然后在 R[2..n] 中选出关键字最小的记录，又需 要做 n-2 次比较。事实上，后面的 n-2 次比较中，有许多比较可能在前面的 n-1 次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排 序时又重复执行了这些比较操作 . 堆排序可通过树形结构保存部分比较结果，可减少比较次数。 ".
3.
