C++实现堆排序示例

下面就详细讲解一下“C++实现堆排序示例”的完整攻略。

什么是堆排序

堆排序是一种树形选择排序方法，它是通过将待排序的序列构建成一个堆，在堆中，全局最大或最小的元素总是位于根节点，根节点最大或最小的元素会被输出到一个新的序列中，再将剩余的元素重新构建成堆进行下一轮循环，直到所有元素均被输出为止。

实现步骤

堆排序主要有两个步骤：构建堆和调整堆。

构建堆

• 将待排序的序列构造成一个大根堆。
• 从最后一个非叶子节点开始从下到上，从右到左调整每个节点的位置，使其满足堆的性质。

以下是一个示例：

void MaxHeapify(int arr[], int start, int end)
{
    // 获取左右子节点的位置
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) {
        // 如果右子节点存在且大于左子节点，则定位到右子节点
        if (son + 1 <= end && arr[son] < arr[son + 1])
            son++;
        // 如果父节点的值大于等于子节点的值，则退出
        if (arr[dad] >= arr[son])
            return;
        // 否则，交换父节点和子节点，并继续向下调整
        else {
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}
void HeapSort(int arr[], int len)
{
    // 构建堆
    for (int i = len / 2 - 1; i >= 0; i--)
        MaxHeapify(arr, i, len - 1);
    // 调整堆
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        MaxHeapify(arr, 0, i - 1);
    }
}

调整堆

构建好大根堆之后，便可以调整堆进行排序了。具体步骤如下：

• 将堆顶元素（最大值）和堆底元素交换位置，每次交换将堆的元素个数减一。
• 对剩余的元素重新进行堆的调整，使得堆的性质得以保持。

以下是一个示例：

void MaxHeapify(int arr[], int start, int end)
{
    // 获取左右子节点的位置
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) {
        // 如果右子节点存在且大于左子节点，则定位到右子节点
        if (son + 1 <= end && arr[son] < arr[son + 1])
            son++;
        // 如果父节点的值大于等于子节点的值，则退出
        if (arr[dad] >= arr[son])
            return;
        // 否则，交换父节点和子节点，并继续向下调整
        else {
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void HeapSort(int arr[], int len)
{
    // 构建堆
    for (int i = len / 2 - 1; i >= 0; i--)
        MaxHeapify(arr, i, len - 1);
    // 调整堆
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        MaxHeapify(arr, 0, i - 1);
    }
}

示例

以下是一个示例说明：

int main()
{
    int n;
    cout << "请输入数组元素的个数：" << endl;
    cin >> n;
    int arr[n];
    cout << "请输入" << n << "个数字：" << endl;
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 利用堆排序排序
    HeapSort(arr, n);

    // 输出排序好的序列
    cout << "排序好的序列为：" << endl;
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

运行结果如下：

请输入数组元素的个数：
5
请输入5个数字：
4 5 3 2 1
排序好的序列为：
1 2 3 4 5

通过上面的示例可以看到，堆排序是一种高效的排序方法，能够快速地对待排序序列进行排序。