1、堆排序首先满足堆的定义,完全二叉树(倒数第二层及以上填满元素)
2、以升序为例,堆化为大顶堆
3、堆化程序
public static void heapify(int[] arr, int i, int length){
int temp = arr[i];
//记录开始比较元素的数值
for(int k = 2 * i + 1; k < length; k = 2 * k + 1){
// 2i+1是比较元素的左子节点
// k // 2k+1是左子节点的左子节点,(越接近堆顶的堆化,越可能涉及比较子节点的子节点的大小,即用上2k+1的循环,第一次排序前,进行整棵树的堆化,由下→上,由右→左进行堆化)(这个顺序是根据数组索引来的)如图1, 图1 第一次排序前堆化顺序 if(k + 1 < length && arr[k] < arr[k + 1] ){ // 保证不越界的情况下,进行左子节点与右子节点的比较,找出较大的值 k++; // 若满足,即右子节点大,将k++,取到右子节点索引 } if(arr[k] > temp){ // 比较左、右子节点中较大的与temp的关系 arr[i] = arr[k]; // 若子节点数值大,则将待比较的初始位置元素替换为子节点数值 i = k; // 未进行arr[k] = temp 原因,多次比较的话,若大一次就替换一次,会有较多的替换操作,i = k 直接定位到较大元素的索引,之后迭代,将最初始的temp,与子树下的节点比较,中间若有需要替换也可根据索引arr[i] = arr[k]进行替换了,因为第二次以及之后的比较前有i = k。 } else{ break; // 若左、右子节点数值不如temp大,则不用比较啦,退出。原因:第一次排序前,进行整棵树的堆化,由下→上,由右→左进行堆化,见图1 } } //for循环结束后,即各个需要比较的子节点均与temp进行比较,最后一个大于temp的元素索引k赋值给了i,i=k,将temp值赋给它。 arr[i] = temp; } //交换数组元素 public static void swap(int[] arr, int a, int b){ int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } //排序部分 public static void heapSort(int[] arr){ for(int i = (arr.length - 1 - 1) / 2 ; i >= 0; i--){ // 第一次排序前的堆化起始索引: arr.length - 1 - 1 /2 // i>=0 是由下→上,由右→左进行堆化,到达堆顶,对应数组索引为0 heapify(arr,i,arr.length); } //堆化完进行堆顶和堆尾元素交换(索引分别为0和arr.length - 1),之后再进行堆化交换,第一次排序后的堆化只有堆顶无序,其他的元素都按照之前的堆化排列完毕,所以heapify(int[] arr,int i,int length)中开始堆化的索引i=0,长度length也是每次递减,所以需要使用循环变量作为参数 for(int j = arr.length - 1; j > 0; j--){ swap(arr,0,j); heapify(arr,0,j); } } ****----------------程序----------------****import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int[] arr = {4,6,8,5,9,14,10,11,12};
System.out.println("堆排序前:");
System.out.println(Arrays.toString(arr));
heapSort(arr);
System.out.println("堆排序后:");
System.out.println(Arrays.toString(arr));
}
public static void heapify(int[] arr, int i, int length) {
int temp = arr[i];
for (int k = 2 * i + 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;
}
}
arr[i] = temp;
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void heapSort(int[] arr) {
for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
heapify(arr, i, arr.length);
}
for (int j = arr.length - 1; j > 0; j--){
swap(arr,0,j);
heapify(arr,0,j);
}
}
}



