堆排序 平均时间复杂度为 O(nlogn) 最坏情况下O(nlogn)
原理 （以从小到大为例）
首先将数组中的数据构建大根堆 具体代码如下
for(i=n/2-1;i>=0;i--){//建成大根堆
while(2*i+1<n){ //存在左右子树
j=2*i+1;//左子树
if((j+1)<n){//右子树存在的情况
if(a[j]<a[j+1]) j++;//如果右子树比做左子树大 j指向 右子树
}
if(a[i]<a[j]){//如果 子节点大于根节点进行交换
t=a[j];
a[j]=a[i];
a[i]=t;
i=j;//调整子树
}else{
break;//不需要调整
}
}
}
构建大根堆结束后下来进行排序 由于是大根对 则根节点就是当前最大值 交换该值重新构造大根堆
重复上述具体代码如下
for(i=n-1;i>0;i--){//依次遍历
t=a[0]; //与第i个数据进行交换 将最大值 插入到该在的地方
a[0]=a[i];
a[i]=t;
k=0;
while(2*k+1<i){//更换根节点后 堆中元素数量减少 重新构造大根堆
j=2*k+1;//左子树
if((j+1)<i){//右子树存在的情况
if(a[j]<a[j+1]) j++;//如果右子树比做左子树大 j指向 右子树
}
if(a[k]<a[j]){
t=a[j];
a[j]=a[k];
a[k]=t;
k=j;//调整子树
}else{
break;//不需要调整
}
}
}
完整代码如下
/*先建成 大根堆 然后每次取a0 的数据此时的数据为最大值 调整堆结构 使最大值依旧在a0 上
-
flag为true 从小到大 false 从大到小
*/
public class Pile_Sort {public void pile_sort(int a[],boolean flag){
int i=0,j=0,h=0,k=0,t;
int n=a.length;
for(i=n/2-1;i>=0;i--){//建成大根堆
while(2i+1<n){
j=2i+1;//左子树
if((j+1)<n){//右子树存在的情况
if(a[j]<a[j+1]) j++;///如果右子树比做左子树大 j指向 右子树
}
if(a[i]<a[j]){
t=a[j];
a[j]=a[i];
a[i]=t;
i=j;//调整子树
}else{
break;//不需要调整
}
}
}
for(i=n-1;i>0;i--){//依次遍历
t=a[0]; //与第i个数据进行交换
a[0]=a[i];
a[i]=t;
k=0;
while(2k+1<i){//更换根节点后 堆中元素数量减少
j=2k+1;//左子树
if((j+1)<i){//右子树存在的情况
if(a[j]<a[j+1]) j++;///如果右子树比做左子树大 j指向 右子树
}
if(a[k]<a[j]){
t=a[j];
a[j]=a[k];
a[k]=t;
k=j;//调整子树
}else{break;//不需要调整 } } } if(!flag){//如果flag 为false 则从大到小排序 此时我们交换前后顺序 n=a.length-1; for(i=0;i<a.length/2;i++){ t=a[i]; a[i]=a[n-i]; a[n-i]=t; } }}
}
