public class HeapSort{
public static void main(String[] args) {
int arr[] = {1,4,2,3,6,7,8,9,10,4};
for(int i=arr.length;i>0;i--){
for(int j=i/2-1;j>=0;j--){ //从最大的非叶子节点开始
adjustHeap(arr,j,i);
swap(arr,0,i-1);
}
}
//打印排序后的数组
StringBuffer sb = new StringBuffer();
for(int m=0;m<arr.length;m++){
sb.append(arr[m]).append(",");
}
System.out.println(sb.toString());
}
//参数:i 数组的下标(0开始计数),len为当前参与排序的数组真实长度(1开始计数)
public static void adjustHeap(int arr[], int i,int len){
int temp = arr[i];
for(int k=2*i+1;k<len;k=2*k+1){ //k=2*k+1,保证在当前节点未移动时,继续向下遍历
//其中k=2*i+1为i节点的左子树,k=2*i+1为i节点的右子树
if(k+1<len && arr[k]<arr[k+1]){
k=k+1;
}
if(arr[k]>arr[i]){
arr[i] = arr[k];
i = k; //这个存值,是为了识别替换的位置,执行arr[i] = temp;
}
}
arr[i] = temp;
}
public static void swap(int arr[],int start,int end){
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
}
堆排序
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- https://blog.csdn.net/qq_25800311/article/details/8976254...
- 前言 堆的数据结构我们在这里不详述,堆排序总的来说一共就两步,即建立一个队使用的方式的HeapInsert和当堆顶...
- 堆基本概念 堆排序是一个很重要的排序算法,它是高效率的排序算法,复杂度是O(nlogn),堆排序不仅是面试进场考的...