乐趣区

关于算法:数组排序之堆排序c实现

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

问题形容

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

剖析:

  1. 组建堆,第 i 个节点和其左右孩子别离对应第 2 i + 1 和 2 i + 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;
    } 

    后果如下

退出移动版