堆排序

堆排序 算法 C/C++

算法思想

假设有一个数组data[N]，从0开始，基本操作为调整堆（adjustHeap)，那么堆排序（升序-最大堆）的过程如下：
1.建堆（buildHeap)：从data[N/2-1]开始，到data[0]结束，每次都是一次adjustHeap的操作。
2.把堆顶元素调到最后，再来进行adjustHeap，由后往前，一直到整个data遍历完。堆排序过程完毕。

算法实现

void adjustHeap(int *data, int node, int length)  //调整堆 
{
    int lchild = 2 * node + 1;       //i的左孩子节点序号 
    int rchild = 2 * node + 2;     //i的右孩子节点序号 
    int parent = node;
    while (lchild <= length-1)  //左孩子在堆里
    {
        if (rchild <= length-1)  //若右孩子也在堆里
        {
            if (data[rchild] > data[lchild])  //左孩子比右孩子小
            {
                // 右孩子与父亲节点比较
                if (data[parent] < data[rchild])
                {
                    Swap(&data[parent], &data[rchild]);
                    parent = rchild;
                    lchild = parent * 2 + 1;
                    rchild = parent * 2 + 2;
                    continue;
                }
                else
                    break;
            }
        }
        if (data[lchild] > data[parent]) //左孩子大于父亲节点
        {
            Swap(&data[lchild], &data[parent]);
            parent = lchild;
            lchild = parent * 2 + 1;
            rchild = parent * 2 + 2;
        }
        else
            break;
    }
}

void buildHeap(int *data, int length)    //建堆 
{
    for (int i = length / 2 - 1;i >= 0;i--)    //非叶节点最大序号值为length/2 - 1 
    {
        adjustHeap(data, i, length);
    }
}

void HeapSort(int *data, int length)    //堆排序 
{
    // 0.异常情况
    if (data == NULL || length <= 0)
        return;
    int i;
    // 建堆
    buildHeap(data, length);
    // 调整堆顶元素，并进行堆调整
    for (i = length-1;i >= 1;i--)
    {
        Swap(&data[0], &data[i]);    //交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面 
        adjustHeap(data, 0, i);      //重新调整堆顶节点成为大顶堆
    }
}