class HeapAdjust{//调整为大顶堆
public void MaxAdjust(int[] arr,int s,int m) {//s为父结点，m为结点数目
int temp=arr[s];//暂存父结点
int j;
for(j=2*s+1;j<m;j=2*s+1) {//j=2*s+1即寻找s的子结点 子节点分别为2s+1,2s+2
if(j+1<m&&arr[j]<arr[j+1])
++j;
if(temp>arr[j])
break;
arr[s]=arr[j];
s=j;
}
arr[s]=temp;
}
public void swap(int[] arr,int s,int m) {
int temp2;
temp2=arr[s];
arr[s]=arr[m];
arr[m]=temp2;
}
}
public class HeapSort {
public static void main(String[] args) {
int[] arr= {50,10,40,60,30,20,70,80,90};
int len=arr.length;
HeapAdjust adjust=new HeapAdjust();
for(int i=(len-1)/2;i>=0;i--) {//调整为大顶堆
adjust.MaxAdjust(arr, i, len);
}
for(int i=len-1;i>=0;i--) {
adjust.swap(arr, 0, i);//将最大的元素至于堆底
adjust.MaxAdjust(arr, 0, i-1);//重新调整为大顶堆
}
System.out.println("调整后的堆序列为：");
for(int i=0;i<arr.length;i++) {
System.out.print(arr[i]+" ");
}
}
}
Python实现堆排序
def HeapAdust(items,s,m): #s为传入的父结点，m为列表的长度
temp=items[s] #暂存父节点
j=2*s+1 #s父节点下的子节点
while j<m:
if items[j]<items[j+1]:
j=j+1
if temp>items[j]:
break
items[s]=items[j]
s=j #将子结点的下标存起来
j=2*s+1 #下一个结点
items[s]=temp
def swap(items,s,m): #交换两个数
temp=items[s]
items[s]=items[m]
items[m]=temp
if __name__=="__main__":
arr=[10,40,30,90,50,60,80,70,20]
length=len(arr)
b=length-1
a=(length-1)//2
for i in range(a,-1,-1): #将父结点进行遍历,调整为大顶堆
HeapAdust(arr,i,length)
for j in range(b,0,-1):
swap(arr,0,j)
HeapAdust(arr,0,j-1) #重新调整为大顶堆
print(arr)
