堆排序

 

　　数据结构课上学过冒泡排序、选择排序、合并排序、快速排序等等，但就是没有堆排序。以前一看到堆，就觉得是个代码很复杂的算法，而且已经有这么多同等速度的排序算法了，没必要看堆排序了。但是最近看面试题发现有大量的关于堆的知识题，所以还是得看看，看了一下发现挺简单的，而且有其他排序算法没有的优点：支持插入删除，获取极值。

代码如下：

#include <iostream>
#include <stdio.h>
using namespace std;
const int n = 1e4 + 5;
int a[n];

void shiftdown(int* data,int index,int number) {
    int fa = index;
    int son = fa * 2 + 1;
    while (son< number) {
        if (son + 1 < number && data[son + 1] < data[son]) son++;
        if (data[fa]>data[son]) {
            swap(data[fa], data[son]);
            fa = son;
            son = fa * 2 + 1;
        }
        else {
            break;
        }
    }
}
void sort(int* data,int number) {
    for (int i = number / 2 - 1; i >= 0; i--) {
        shiftdown(data, i, number);
    }
    //sort
    for (int i = number - 1; i >= 0; i--) {
        swap(data[0], data[i]);
        shiftdown(data, 0, i);
    }
}
int main()
{
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
}