数组排序之堆排序，c++实现

问题形容

采纳堆排序的办法去排序一个数组{47, 35, 26, 20, 18, 7, 13, 10}
数组对应堆的图例，根节点大于左右孩子节点

剖析：

  1. 组建堆，第i个节点和其左右孩子别离对应第2i + 1和2i + 2下标的数据
  2. 如何确定堆有几层？如下
  3. 数组的最初一个值的下标为n其父节点为i，所以存在关系n = 2*i+1 => i = (n-1)/2
  4. 即第0~i个节点是有子节点，i+1~n个节点是叶子节点
  5. 首次建堆解决，把树解决层，根节点大于或等于其左右孩子的树
  6. 首次建堆后的数据是大根堆，然而此时从上往下，从左往右并不是有序的
  7. 然首次建堆不是有序的，然而此时堆顶元素必定是最大的
  8. 因而把堆顶元素和数组最初一个元素替换地位，而后剔除掉最初一个元素，从新建堆
  9. 为此时，除了第一个元素，其余元素都是合乎大根堆关系的，因而，从0开始建堆（不同于一开始的，以每一个小节点建堆，再逐渐组装起来）

  10. 最初的堆顶元素是最大的，反复7、8步骤，直到全副元素处理完毕。

    算法实现

    #include<iostream>using namespace std;class Heap { private:     int arr[10] = {47, 35, 26, 20, 18, 7, 13, 10, 8, 6}; public:      void show();     void sort(int n);     void sortHeap(int k, int n); // 在以后节点中排序 };void Heap::show() { for (int i = 0; i < 10; i++) {     cout<<this->arr[i]<<" ";  } cout<<endl;}// n 示意数组长度，k示意该根节点的下标 void Heap::sortHeap(int k, int n) { int i, j, temp; i = k; j = 2 * i + 1; // 操作第k层和其孩子比拟 while(j < n) {     // 在数组边界内, 比拟左右孩子，较大的孩子与根节点比拟      if (j < n-1 && this->arr[j] < arr[j+1]) j++;     if (this->arr[i] > this->arr[j]) {         break;     } else {         temp = this->arr[i];         this->arr[i] = this->arr[j];         this->arr[j] = temp;         this->show();         // 替换后，前面可能存在大于改根节点的值，所以替换后的节点作为根节点，持续比拟，直到条件不成立         i = j; j = 2*i+1;     } }}void Heap::sort(int n) { int i, temp; // 从后往前遍历有根节点，最初一个根节点的下标n=2*i+1 => i = (n-1) / 2失去根节点  for (i = (n-1)/2; i >= 0; i--) {     this->sortHeap(i, n);     this->show(); } cout<<"---"<<endl;  // 将堆顶的数值和最初一个未替换过的下标的值替换，失去的下标n-i是目前未解决的最大的数值 for (i = 1; i <= n-1; i++) {     cout<<"堆顶"<<this->arr[i]<<endl;      temp = this->arr[0]; this->arr[0] = this->arr[n - i]; this->arr[n-i] = temp;     // 从新建队，n-i个节点下标后曾经是解决过的值，不须要在堆中解决      this->sortHeap(0, n-i); } this->show();}int main() { Heap heap;//    heap.show(); heap.sort(10); heap.show(); return 0;}

    后果如下