Java堆排序是什么
这篇文章主要讲解了“Java堆排序是什么”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“Java堆排序是什么”吧！
枞阳网站制作公司哪家好，找成都创新互联！从网页设计、网站建设、微信开发、APP开发、成都响应式网站建设公司等网站项目制作，到程序开发，运营维护。成都创新互联于2013年创立到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选成都创新互联。
堆是指具有下列性质的完全二叉树 完全二叉树 i的双亲是[i/2]
根节点一定最大或者最小 ！
1 每个节点的值>=其左右节点的值 大顶堆
2 每个节点的值<=其左右节点的值 小顶堆
堆排序 Heap Sort 就是利用堆进行排序 如大顶堆。 将带排序的数列构造程一个大顶堆 然后将跟节点与堆数组末尾元素互换，然后将剩下的n-1个序列重新构造成堆 往返进行。
堆排序（Heap Sort）只需要一个记录元素大小的辅助空间（供交换用），每个待排序的记录仅占有一个存储空间。
堆的存储
一般用数组来表示堆，若根结点存在序号0处， i结点的父结点下标就为(i-1)/2。i结点的左右子结点下标分别为2*i+1和2*i+2。
（注：如果根结点是从1开始，则左右孩子结点分别是2i和2i+1。）
如第0个结点左右子结点下标分别为1和2。
如最大化堆如下：
左图为其存储结构，右图为其逻辑结构。
1.如何由一个无序序列建成一个堆？
2.如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？
堆排序方法对记录数较少的文件并不值得提倡，但对n较大的文件还是很有效的。因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。
堆排序在最坏的情况下，其时间复杂度也为O(nlogn)。相对于快速排序来说，这是堆排序的最大优点。此外，堆排序仅需一个记录大小的供交换用的辅助存储空间。
堆排的时间复杂度为O(n log n). 不稳定
#include <iostream>
#include <cstring>
using namespace std;
void HeapAdjust1(int a[], int pos, int n)//这个不太好理解
{
int temp = a[pos];
int child = 2*pos+1;
while(child<n)
{
if(child+1<n && a[child]<a[child+1])
{
child++;
}
if(a[pos]<a[child])
{
a[pos] = a[child];
pos = child;
child = 2*child+1;
}
else
{
break;
}
}
a[pos] = temp;
}void HeapAdjust(int a[], int pos, int n)
{
int max = pos;
int Left = 2*pos+1;
int Right = 2*pos+2;
if(pos<=(n-1)/2)
{
if(Left<n && a[max]<a[Left])
{
max = Left;
}
if(Right<n && a[max]<a[Right])
{
max = Right;
}
if(pos != max)
{
int temp =a[pos];
a[pos] = a[max];
a[max] = temp;
HeapAdjust(a, max,n);//避免调整之后以max为父节点的子树不是堆
}
}}
void BuildHeap(int a[], int n)
{
for(int pos=(n-1)/2;pos>=0; --pos)
{
HeapAdjust(a,pos,n);
}
}
void HeapSort(int a[], int n)
{
BuildHeap(a, n);
for(int len = n-1;len>0; --len)
{
int temp = a[len];
a[len] = a[0];
a[0] = temp;
HeapAdjust(a, 0, len);
}
}
int main()
{
int a[9] = {9,1,5,8,3,7,4,6,2};
//ShellSort(a, 9);
HeapSort(a, 9);
for(int i=0;i<9;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}感谢各位的阅读，以上就是“Java堆排序是什么”的内容了，经过本文的学习后，相信大家对Java堆排序是什么这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是创新互联，小编将为大家推送更多相关知识点的文章，欢迎关注！
网站栏目：Java堆排序是什么
分享路径：https://www.cdcxhl.com/article14/jsiede.html
成都网站建设公司_创新互联，为您提供建站公司、做网站、用户体验、微信小程序、网站导航、App开发
声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联
