堆排序

堆排序是一种选择排序，下面介绍从大到小的堆排序算法，用小根堆。

小根堆的筛选算法：

void sift(int data[], int k, int m)
{
    int i = k ,int j = 2 * k;
    while (j <= m) {
        if (j < m && data[j] > data[j + 1]) ++j;
        if (data[i] < data[j]) break;
        else {
            data[0] = data[i];
            data[i] = data[j];
            data[j] = data[0];
            i = j;
            j = 2 * i;
        }
    }
}

堆排序算法主函数：

void HeapSort(int data[], int n) // index[1, n]
{
    for (int i = n >> 1; i >= 1; --i)
        sift(data, i, n);

    for (int i = 1; i < n; ++i) {
        data[0] = data[1];
        data[1] = data[n - i + 1];
        data[n - i + 1] = data[0];
        sift(data, 1, n - i);
    }
}