您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

堆排序(图文)

第十三双眼睛2023-10-20【数据结构与算法】人已围观

简介堆排序

堆排序

package com.xingchen.day010;
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int[] arr = {4,6,8,5,9,1,-85,1000};
heapSort(arr);
}
public static void heapSort(int[] arr) {
int temp = 0;
//分布完成
//adjust(arr, 1, arr.length);
//System.out.println(Arrays.toString(arr));
//adjust(arr,0,arr.length);
//System.out.println(Arrays.toString(arr));
for (int i = arr.length/ 2 -1; i>= 0 ;i --) {
adjust(arr,i,arr.length);
}
for (int j= arr.length - 1; j>0;j --) {
//交换
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjust(arr, 0, j);
}
System.out.println(Arrays.toString(arr));
}
public static void adjust(int[] arr,int i,int length) {
//i表示非叶子节点的索引
//length表示对多少个元素进行调整
int temp = arr[i];
for (int k = i * 2 + 1; k<length; k = 2 * k + 1) {
if (k + 1 < length && arr[k] < arr[k+1]) {//说明左子节点的值小于右子节点的值
k ++;
}
if (arr[k] > temp) {
arr[i] = arr[k];
i = k;
} else {
break;
}
}
//当for循环结束后，已经将i为父节点为最大值放在了最顶上
arr[i] = temp;
}
}

Tags：

很赞哦！ ()

上一篇：线索化二叉树(图文)

下一篇：赫夫曼树(图文)