对71,53,46,84,213,20,16,32,52,108,66,97实现堆排序给出c++代码并进行算法的基本思想及复杂度分析以及对调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训
时间: 2024-09-20 09:04:19 浏览: 32
堆排序是一种基于比较的排序算法,它利用了二叉堆的数据结构特性。首先将待排序数组构建成一个大顶堆(最大堆),然后每次取出堆顶元素(最大值),将其放到已排序部分的末尾,再调整剩余部分使之重新成为大顶堆。这个过程反复进行,直到所有元素都被排序。
以下是C++实现堆排序的基本代码:
```cpp
#include <vector>
using namespace std;
// 堆ify操作,保持父节点大于子节点
void heapify(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) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
// 主函数,进行堆排序
void heapSort(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--) {
swap(arr[0], arr[i]); // 将最大元素移至末尾
heapify(arr, i, 0); // 调整剩余部分为堆
}
}
// 示例
int main() {
vector<int> numbers = {71, 53, 46, 84, 213, 20, 16, 32, 52, 108, 66, 97};
heapSort(numbers);
for (auto num : numbers)
cout << num << " ";
return 0;
}
```
堆排序的时间复杂度:
- 建堆阶段:O(n),因为需要从最后一个非叶子节点开始向上调整每个节点。
- 排序阶段:总共进行n-1轮交换,每轮调整堆需要logn时间,所以总时间为O(n log n)。
调试和运行问题:
- 输入数据有误:检查输入数组是否为空,大小是否合理。
- 空指针异常:确保传递给heapify和heapSort的arr不是空指针。
- 数组越界:堆操作可能会导致数组下标越界,需确保循环条件正确。
经验和教训:
- 对于数组长度较大的情况,堆排序效率较高,适合大量数据排序。
- 需要注意的是堆排序不是稳定的排序算法,相等元素的相对位置可能会改变。如果稳定性很重要,可以选择其他稳定排序算法如归并排序。
阅读全文