堆排序

https://blog.csdn.net/guoweimelon/article/details/50904231

一、堆排序（Heap sort）是指利用堆（最大堆、最小堆）这种数据结构所设计的一种排序算法。堆是一个完全二叉树的结构，并同时满足如下性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

二、构建最大堆得到的是升序排列；构建最小堆得到的是降序排列。


堆排序算法如下：

1、创建一个最大（小）堆H；

2、把堆首和堆尾元素互换；

3、把堆的大小减1，重新构造一个最大（小）堆；

4、重复步骤2、3，直到堆的大小减少为1。

#include<iostream>
#include <stdio.h> 
#include <stack> 

using namespace std;


void counstruct_max_heap(int* a, int position, int end) {
    int parent_pos = position;
    int child_pos = 2 * position + 1;
    
    while (child_pos < end) {
        if (child_pos + 1 < end && a[child_pos] < a[child_pos + 1]) {
            child_pos ++;
        }
        if (a[parent_pos] > a[child_pos]) {
            return;
        }
        else
        {
            swap(a[parent_pos], a[child_pos]);
            
　　　　　　　parent_pos = child_pos;
            child_pos = 2 * parent_pos +1;
        }
    }
}

void max_heap_sort(int* a, int begin, int end) {
    for (int i = end / 2; i >=0; i--) {
        counstruct_max_heap(a, i, end);
    }
    for (int i= end-1; i>=0; i--) {
        swap(a[0], a[i]);
        counstruct_max_heap(a, 0, i);
    }
}

int main()
{
    int a[8] = {4, 2, 6, 7, 9, 5, 1, 3};
    int length = sizeof(a) / sizeof(a[0]);
    
    max_heap_sort(a, 0, length);
    for(int i=0; i < 8; i++) {
        cout << a[i] << " " << endl;
    }
    return 0;
}