使用动态数组实现堆排序

介绍

在本实验中，你将学习如何使用 C++ 中的动态数组实现堆排序（Heap Sort）算法。堆排序是一种基于比较的排序算法，它通过将输入分为已排序和未排序区域，并通过反复从未排序区域中提取最大或最小元素并将其移动到已排序区域来缩小未排序区域。

创建动态数组

我们将在 ~/project 目录下使用以下命令创建一个名为 main.cpp 的新文件：

touch ~/project/main.cpp

首先，我们将创建一个动态数组来存储元素。我们将使用 new 操作符在程序运行时动态分配内存。

int* arr;
arr = new int[size];

Heapify 函数

接下来，我们将创建 heapify() 函数来重新排列数组中的元素。heapify() 函数的目的是维护堆属性，即每个节点都大于或等于其子节点。

void heapify(int* arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

堆排序函数

在实现 heapify() 函数之后，我们将创建 heapSort() 函数以升序排列数组。

void heapSort(int* arr, int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

主函数

最后，我们将创建 main() 函数，用于从用户读取元素并使用堆排序算法显示排序后的数组。

int main() {
    int size;
    cout << "Enter the number of elements: ";
    cin >> size;

    int* arr;
    arr = new int[size];

    cout << "Enter the elements: ";
    for (int i = 0; i < size; i++) {
        cin >> arr[i];
    }

    heapSort(arr, size);

    cout << "Sorted Array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    delete[] arr;
    return 0;
}

总结

在本实验中，你学习了如何使用 C++ 中的动态数组实现堆排序算法。你还学习了如何创建动态数组、对数组进行堆化（heapify）以及排序数组以升序显示排序后的数组。按照说明运行示例代码，并练习实现堆排序算法。