#include <iostream> #include <vector> // 调整堆 void heapify(std::vector<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) { std::swap(arr[i], arr[largest]); heapify(arr, n, largest); } } // 堆排序 void heapSort(std::vector<int>& arr) { int n = arr.size(); // 建立最大堆 for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // 排序 for (int i = n - 1; i > 0; i--) { std::swap(arr[0], arr[i]); heapify(arr, i, 0); } } // 数组倒序 void reverseArray(std::vector<int>& arr) { int start = 0; int end = arr.size() - 1; while (start < end) { std::swap(arr[start], arr[end]); start++; end--; } } int main() { std::vector<int> arr = {}; // 堆排序 heapSort(arr); std::cout << "堆排序后的数组："; for (int num : arr) { std::cout << num << " "; } std::cout << std::endl; // 数组倒序 reverseArray(arr); std::cout << "数组倒序结果："; for (int num : arr) { std::cout << num << " "; } std::cout << std::endl; return 0; }注释

时间: 2024-04-16 21:30:06 浏览: 132

这是一个包含堆排序和数组倒序功能的程序。它使用了两个函数：heapify和heapSort。 heapify函数用于调整堆。它接受一个整数向量arr，以及堆的大小n和当前节点的索引i。在该函数中，先将当前节点设为最大元素的索引，然后比较当前节点与左右子节点的大小，如果子节点中存在比当前节点更大的元素，则将最大元素的索引更新为子节点的索引。最后，如果最大元素的索引不等于当前节点的索引，则交换这两个元素，并递归地调用heapify函数。 heapSort函数用于对数组进行堆排序。它接受一个整数向量arr，并按照以下步骤进行排序：首先，通过调用heapify函数，将数组构建成最大堆；然后，从最后一个元素开始，依次将根节点（最大值）与当前元素交换，并调用heapify函数对剩余元素进行调整；重复这个过程，直到所有元素都排好序。 reverseArray函数用于将数组倒序。它接受一个整数向量arr，并使用两个指针start和end来交换元素，以实现数组的倒序。在主函数中，程序首先定义了一个空的整数向量arr。然后，它调用heapSort函数对arr进行排序，并输出排序后的结果。接着，它调用reverseArray函数对arr进行倒序，并输出倒序后的结果。最后，程序返回0表示正常运行结束。如果你对这段代码有任何疑问，请随时提问。

相关问题

设计一个c++堆排序，输出每一趟的排序结果。不用vector

设计一个C++堆排序算法并打印每趟的排序结果，我们可以使用数组而不是`std::vector`。以下是堆排序的基本步骤： 1. **建立大顶堆**： - 从最后一个非叶子节点开始，向下调整堆，保证每个节点都大于其子节点。 2. **交换根元素与最后一个元素**： - 将当前最大值（即堆顶）与最后一个元素交换，然后将剩余元素重新调整为大顶堆。 3. **重复步骤1和2**，直到整个数组有序。这是一个简单的堆排序示例： ```cpp #include <iostream> 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) { std::swap(arr[i], arr[largest]); heapify(arr, n, largest); } } 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--) { std::swap(arr[0], arr[i]); // 交换最大值到末尾 heapify(arr, i, 0); // 调整剩余部分成新堆 std::cout << "After swap at index " << i << ": "; printArray(arr, i); // 打印当前排序状态 } } void printArray(int arr[], int n) { for (int i = 0; i < n; ++i) std::cout << arr[i] << " "; std::cout << std::endl; } int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int n = sizeof(arr) / sizeof(arr[0]); heapSort(arr, n); return 0; } ``` 在这个代码中，`heapify`函数用于维护大顶堆结构，`heapSort`函数则实现了整个排序过程，并在每次交换后打印数组。运行这个程序，你会看到每趟排序后的结果。

阅读全文

相关推荐

CSDN会员

开通CSDN年卡参与万元壕礼抽奖

海量 VIP免费资源千本正版电子书商城会员专享价千门课程&专栏

全年可省5,000元立即开通