4、堆排序
过程：
-
建立大根堆
- 找到最后一个非叶子节点（即 i = n/2），将它和最大的孩子节点互换（若它大于孩子，则不用换）
- 然后从后往前 依次遍历非叶子节点，并按要求调整
- 如果在遍历过程中，上面的节点因为要调整 导致下面原来弄好的堆结构被破坏了，此时在调整完上面的节点后 还要再调整下面的节点（只要调整一次上面的节点，那么下面的节点也要跟着调整）
//将一个无序数组改造成按大根堆排布的数组void BuildMaxHeap(vector<int>& a,int size){for(int i=a.size()/2;i>=0;i--)HeapAdjust(a,i,size);}//把以i为父节点的结构调整为堆void HeapAdjust(vector<int>&a,int k，int size)//这里要写一下这个数组的范围，因为很多时候只需要让数组的前一部分建立堆的秩序，如堆排序{int x=a[k];//记录当前非叶子节点即父节点的值//k是父节点，i表示左孩子，i+1表示右孩子for(int i=2*k;i<size;i*=2){if(i+1<size&&a[i+1]>a[i])//比较左右孩子谁更大,让更大的孩子节点继续执行后序内容i++;if(x>a[i])//比较父节点和最大的孩子节点break;//若父节点更大，说明满足大根堆，直接不用调整了，退出循环else//如果孩子节点更大{a[k]=a[i];//则让这个孩子节点的值作为父节点的值k=i;//更新k值。现在聚焦这个孩子节点，下一轮就是看这个孩子节点的孩子节点了，原来的a[k]的值不断地往下传递//下一轮循环中，我们要判断原来父节点的值在向下调整之后会不会破坏下面的堆结构} }a[k]=x; }
-
堆排序：
- 先构造大根堆，然后基于得到的大根堆，将 堆顶元素 和 待排序序列的最后一个元素 互换位置
- 交换元素过后，都要再调整之前的大根堆（没必要重新建造，调整即可）
（需要注意的是，每轮都会确定一个元素，所以参与构建大根堆的元素数量也会少一个）
void HeapSort(vector<int>&a, int size){BuildMaxHeap(a,size);for(int i=size-1;i>=2;--i){swap(a[0],a[size-1]);HeapAdjust(a,0,i);}}
- 整体代码：
#include<iostream>#include<vector>using namespace std;void HeapAdjust(vector<int>& a, int k, int size);//将一个无序数组改造成按大根堆排布的数组void BuildMaxHeap(vector<int>& a, int size){for (int i = a.size() / 2; i >= 0; i--)HeapAdjust(a, i, size);}//把以i为父节点的结构调整为堆void HeapAdjust(vector<int>& a, int k, int size)//这里要写一下这个数组的范围，因为很多时候只需要让数组的前一部分建立堆的秩序，如堆排序{int x = a[k];//记录当前非叶子节点即父节点的值//k是父节点，i表示左孩子，i+1表示右孩子for (int i = 2 * k; i < size; i *= 2){if (i + 1 < size && a[i + 1] > a[i])//比较左右孩子谁更大,让更大的孩子节点继续执行后序内容i++;if (x > a[i])//比较父节点和最大的孩子节点break;//若父节点更大，说明满足大根堆，直接不用调整了，退出循环else//如果孩子节点更大{a[k] = a[i];//则让这个孩子节点的值作为父节点的值k = i;//更新k值。现在聚焦这个孩子节点，下一轮就是看这个孩子节点的孩子节点了，原来的a[k]的值不断地往下传递//下一轮循环中，我们要判断原来父节点的值在向下调整之后会不会破坏下面的堆结构}}a[k] = x;}void HeapSort(vector<int>& a, int size){BuildMaxHeap(a, size);for (int i = size - 1; i >= 2; i--){swap(a[0], a[i]);HeapAdjust(a, 0, i);}swap(a[0], a[1]);}int main(){vector<int> nums = { 2,3,6,1,4,5,9,7,8 };HeapSort(nums, nums.size());for (int i = 0; i < nums.size(); i++){cout << nums[i] << endl;}}
-
稳定性：因为堆排序涉及前后交换，相等元素的相对位置是不能保证的，所以不稳定
-
时间复杂度：O（nlogn），其中 建堆：O（n），排序：O（nlogn）；空间复杂度：O（1）