堆排序相对冒泡排序、选择排序效率很高，不再是O（n^2）.
假若将一个序列升序排序好，那么我们来考虑最大堆还是最小堆来排序。假若是最小堆的话，堆的顶端必定是堆中的最小值，这样貌似可以。但是，如果是它的（一边或）子树左子树的节点数据值大于（一边或）右子树的节点数据值，直接打印肯定是错误的，而且对于此时的堆我们也无法操控来调整好正确的顺序了。
那我们换成最大堆来实现升序想，当我们把序列调整成为最大堆后，最大堆顶端的数据值是最大的，然后我们将这个最大值与堆的最后一个叶子节点值来进行交换，再将交换后的顶端值进行调整，换到合适的位置处……重复这样的工作，注意：进行第2次交换就要将顶端元素值与倒数第2个节点元素值交换了，且调整顶端元素位置也不能一直调整到size-1处。（因为：size-1处的值已经是最大）
代码如下：
计算
安全
数据库
网络和加速
企业服务
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include<assert.h>
void AdjustDown(int* a,int parent, int size)
{
int child = 2 * parent + 1;
while (child < size)
{
if (child + 1 < size && a[child] < a[child + 1])
{
++child;
}
if (a[child]>a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
void Print(int*a, int size)
{
cout << "升序序列为："<<endl;
for (int i = 0; i < size; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
void HeapSort(int* a,int size)
{
assert(a);
//建成最大堆
for (int i = (size - 2) / 2; i >=0; i--)
{
AdjustDown(a,i, size);
}
//交换顺序
for (int i = 0; i < size; i++)
{
swap(a[0], a[size - i - 1]);
AdjustDown(a, 0, size-i-1);
}
}
void Test()
{
int arr[] = { 12, 2, 10, 4, 6, 8, 54, 67,100,34,678, 25, 178 };
int size = sizeof(arr) / sizeof(arr[0]);
HeapSort(arr, size);
Print(arr,size);
}
int main()
{
Test();
system("pause");
return 0;
}时间复杂度：
（n-2）/2*lgn+n*(1+lgn)--->O(n).
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
