堆排序
堆有序：二叉树的每个结点都大于等于他的两个子结点，被称为堆有序。
二叉堆：是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存。（不使用数组的第一个位置）
即：k的父结点为k/2;k的子结点为2k和2k+1。
堆中根结点也就是a[1]是二叉树的最大结点。
一棵大小为N的完全二叉树的高度为log2^N+1。
堆排序过程：
堆排序主要分为两部分：
一、是将数组构造为堆有序；
二、是下沉排序，即将堆末元素与堆首交换，然后输出新堆末元素，新堆首元素下沉。
代码：
template<typename Item> void eaxh(Item &a, Item &b) { Item t = a; a = b; b = t; } template<typename Item> void sink(vector<Item>&a, int k, int N)//下沉函数 {//(数组，下沉元素，数组长） while (2 * k <= N) { int j = 2 * k;//子结点 if (j < N&&a[j] < a[j + 1])j++;//选择较大的子结点 if (a[k]>=a[j])break; eaxh(a[k], a[j]);//下沉 k = j; } } template<typename Item> void heapsort(vector<Item>&a)//0位元素不接受排序 { int N = a.size()-1; for (int k = N / 2; k >= 1; k--)//堆有序 sink(a, k, N); while (N > 1)//下沉排序 { eaxh(a[1], a[N--]); sink(a, 1, N); } }
改进：
下沉函数可以动过位移的方式回避交换函数
template<typename Item> void sink(vector<Item>&a, int k, int N)//改进下沉函数 {//移位方式下沉元素 Item temp = a[k];//下沉元素 while (2 * k <= N) { int j = 2 * k; if (j < N&&a[j] < a[j + 1])j++; if (temp >= a[j])break; a[k] = a[j];//移位 k = j; } a[k] = temp;//a[k]为末尾子结点 } 测试用例： int main() { uniform_int_distribution<int> u(0, 100000); default_random_engine e; vector<int> a; for (int i = 0; i <=1000000; ++i) a.push_back(u(e)); heapsort(a); //for (auto i = a.begin() + 1; i < a.end(); i++)//打印动态数组 // cout << *i <<" "; //cout << endl; cout << (double)clock() / CLOCKS_PER_SEC << endl; cout << endl; system("pause"); return 0; } 测试结果：
堆排序测试结果： 算法|量级 101001000100001000001000000堆排序0.1040.1040.1090.1680.7227.418改进0.1030.1060.1070.1560.6356.151 堆排序在排序复杂性的研究中有着重要的地位，因为他是我们所知的唯一能够同时最优化地利用空间和时间的方法——在最坏的情况下他也能保证使用~2NlgN次比较和恒定的额外时间。
但在现代系统中使用较少，因为他无法利用缓存。数组元素很少和相邻的其他元素进行比较，因此缓存未命中率要远远高于别的排序方式。
