6.4堆排序

算法思想： 建立堆（建立过程中时刻维护堆，使其每个子树(堆可看作一个二叉树)都满足堆的定义），堆的根节点值最大，可获得该根节点并删去，将剩下的结点继续调整为堆，依次操作，每次都能获得当前最大元素，最后即为排序结果。 时间复杂度：O(nlgn)；空间复杂度：O(1)(因为可以将每次获得结果直接存储到当前数组里，因此没必要在额外的开辟空间)

代码实现：

#include <iostream> #include <limits> #include<vector> using namespace std; typedef struct Heap { vector<int> A; int HeapSize; }Heap; //因为i是从1开始，对应到数组索引应当减一 //i对应的父节点 int parent(int i) { return i / 2; } //i结点对应的左子节点 int left(int i) { return int(2 * i); } //i结点对应的右子节点 int right(int i) { return int(2 * i + 1); } //维护大顶堆 void MaxHeapify(Heap &A, int i) { int large, tmp; int l = left(i); int r = right(i); //比较左子节点 if((l <= A.HeapSize) && (A.A[l - 1] > A.A[i - 1])) { large = l; } else { large = i; } //比较右子节点 if((r <= A.HeapSize) && (A.A[r - 1] > A.A[large - 1])) { large = r; } //选出左右子节点最大的并于父节点交换，以使满足堆的定义 if(large != i) { tmp = A.A[i - 1]; A.A[i - 1] = A.A[large - 1]; A.A[large - 1] = tmp; MaxHeapify(A, large); } } //建立堆 void BuildMaxHeap(Heap &A) { A.HeapSize = A.A.size(); for(int i = (A.A.size() / 2); i >= 1; i --) { MaxHeapify(A, i); } } //排序 void HeapSort(Heap &A) { int tmp; BuildMaxHeap(A); for(int i = A.A.size(); i >= 2; i --) { tmp = A.A[0]; A.A[0] = A.A[i - 1]; A.A[i - 1] = tmp; A.HeapSize = A.HeapSize - 1; MaxHeapify(A, 1); } } void HeapIncreaseKey(Heap &A, int i, int key) { if(key < A.A[i - 1]) cout << "smaller" << endl; A.A[i - 1] = key; while(i > 1 && A.A[parent(i) - 1] < A.A[i - 1]) { int tmp = A.A[i - 1]; A.A[i - 1] = A.A[parent(i) - 1]; A.A[parent(i) - 1] = tmp; i = parent(i); } } void MaxHeapInsert(Heap &A, int key) { A.HeapSize += 1; A.A[A.HeapSize - 1] = INT_MIN; HeapIncreaseKey(A, A.HeapSize, key); } //插入建堆 void insertBuildMaxHeap(Heap &A) { A.HeapSize = 1; for(int i = 2; i <= A.A.size(); i ++) { MaxHeapInsert(A, A.A[i -1]); } } //采用插入建堆的排序 void intsertBuildHeapSort(Heap &A) { int tmp; insertBuildMaxHeap(A); for(int i = A.A.size(); i >= 2; i --) { tmp = A.A[0]; A.A[0] = A.A[i - 1]; A.A[i - 1] = tmp; A.HeapSize = A.HeapSize - 1; MaxHeapify(A, 1); } } int main() { vector<int> b{4, 1, 3, 2, 16, 9, 10, 14, 8, 7}; Heap A, A1; cout << "插入建堆排序：" << endl; for(vector<int>::iterator it = b.begin(); it != b.end(); it ++) { A1.A.push_back(*it); } intsertBuildHeapSort(A1); for(vector<int>::iterator it = A1.A.begin(); it != A1.A.end(); it ++) { cout << *it <<' '; } cout << "\n普通建堆排序：" << endl; for(vector<int>::iterator it = b.begin(); it != b.end(); it ++) { A.A.push_back(*it); } HeapSort(A); for(vector<int>::iterator it = A.A.begin(); it != A.A.end(); it ++) { cout << *it <<' '; } cout << endl; return 0; }

结果输出：

插入建堆排序： 1 2 3 4 7 8 9 10 14 16 普通建堆排序： 1 2 3 4 7 8 9 10 14 16