c++实现堆排序的示例代码
吴天德少侠 人气:0看了一下优先队列，查了一下堆排序。堆排序主要就是建最大堆（最小堆）和交换2个操作。如果建的是最大堆，那么交换的时候，父节点就和最大的子节点比较，如果它比最大的子节点还大，那就不用比了。因为后面还有一个交换的操作，所以最后得到的就是由小到大的排序；反之，得到的就是由大到小的排序。
#include<iostream>
#include<algorithm>
using namespace std;
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<int>(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 arr[]{ 5,3,4,9,7,8,1,2,10,23,15 };
int len = int(sizeof(arr) / sizeof(*arr));
heapSort(arr, len);
cout << "排序之后:" << endl;
for (auto item : arr) {
cout << item << " ";
}
return 0;
}
这几行代码干的事情，就是如下图所示，由低向高，逐渐生成最大堆，找到最大元素
紧接着的后面的for循环就是最后一个元素和堆顶元素交换，然后重新调整除了交换到后面来的元素，直到只有堆顶一个元素。就排好序了。
加载全部内容