[数据结构与算法]堆排序（c++实现）

? ? ? ? 堆排序是一种选择排序，利用堆这种数据结构来完成选择，其算法思想是将待排序数据构造为一个大根堆（小根堆），然后将堆顶元素与待排序数组最后一个元素进行交换，此时末尾元素就是最大值（最小值），然后将剩余n-1个元素重新构造成大根堆（小根堆），重复以上操作。

? ? ? ? 堆是一个完全二叉树，大根堆满足根结点元素均大于其孩子结点，（小根堆满足根结点元素均小于其孩子结点），大根堆小根堆示意图如下：

? ? ? ? 堆排序用c++实现，自己编写的代码，虽然思想很简单，但是编起来还是遇到了一些bug,不过都已经一一调通，给出待排序数组 v=??{ 4,5,13,6,7,25,22,9 };

#include <iostream>
#include<vector>
using namespace std;

void swap(int &a, int &b)  //定义一个交换函数
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}

void heap_point(vector<int>& v, int m,int i)  //对一个根结点进行heap操作
{
    int max = i;
    if ((2 * i + 1) <= m  && v[max] < v[2 * i + 1])
    {
        max = 2 * i + 1;
    }
    if ((2 * i + 2) <=  m && v[max] < v[2 * i + 2])
    {
        max = 2 * i + 2;
    }
    if (max != i)   
    {
        swap(v[max], v[i]);
        heap_point(v, m, max); //当结点发生了交换之后，要对这个节点进行检查，看其是否满足heap要求

    }
}

void heap(vector<int> &v, int i,int n) //制造大根堆，每操作一次就会产生一个大根堆
{
    int last_node = i ;
    int last_node_parent = (i  - 1) / 2;
    for (int j = last_node_parent; j >= 0; j--)
    {
        heap_point(v, i, j);
    }
}

  void heap_sort(vector<int>& v,int n)  //堆排序
{
      for (int i = n - 1; i >= 0; i--)
      {
          heap(v, i, n); 
          swap(v[0], v[i]);  //每进行一个堆排序，将首节点跟尾结点交换位置，也即将最大值置于底部，
          //然后再对剩下的节点进行堆排序
          
    }
}


int main()
{
    vector<int> v;
    v = { 4,5,13,6,7,25,22,9 };
    cout << "排序前：" << endl;
    for (int i : v)
    {
        cout << i << endl;
    }

    heap_sort(v, 8);

    cout << "排序后：" << endl;
    for (int i : v)
    {
        cout << i << endl;
    }
    
    return 0;
}

运行结果：

排序前：
4
5
13
6
7
25
22
9
排序后：
4
5
6
7
9
13
22
25