堆排序讲解
主方法
public static void main(String[] args) {
int[] arr={4,6,8,5,9};
heapSort(arr);
}
堆排序(第一个非叶子结点)
public static void heapSort(int[] arr) {
System.out.println("堆排序!!");
// 从左到右 从下至上 第一个非叶子结点
adjustHeap(arr,1,arr.length);
System.out.println("第一次"+Arrays.toString(arr));
}
调整堆 (其中break原因是从左到右,由下至上寻找第一个非叶子结点)
public static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];// 先取出当前元素的值,保存到临时变量中
// k节点是i节点的左子节点
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
if (k + 1 < length && arr[k] < arr[k + 1]) {
k++;// k指向i节点的右子节点
}
if (arr[k] > temp) {// 如果子节点大于父节点
arr[i] = arr[k];// 将子节点赋给父节点
i = k; //重点:i指向k
} else {
break; //难点
}
}
arr[i] = temp;
}
堆排序(第二个非叶子结点)
public static void heapSort(int[] arr) {
System.out.println("堆排序!!");
// 从左到右 从下至上 第一个非叶子结点
adjustHeap(arr,1,arr.length);
System.out.println("第一次"+Arrays.toString(arr));
//第二个非叶子结点
adjustHeap(arr,0,arr.length);
System.out.println("第二次"+Arrays.toString(arr));
}
完整的堆排序
public static void heapSort(int[] arr) {
int temp=0;
System.out.println("堆排序!!");
/*// 从左到右 从下至上 第一个非叶子结点
adjustHeap(arr,1,arr.length);
System.out.println("第一次"+Arrays.toString(arr));
//第二个非叶子结点
adjustHeap(arr,0,arr.length);
System.out.println("第二次"+Arrays.toString(arr));*/
//1.将无序序列构成升序的大顶堆
for (int i=arr.length/2-1;i>=0;i--){
adjustHeap(arr,i,arr.length);
}
//2.将堆顶元素与末尾元素交换,将最大元素放到末尾
//3.重新调整结构,使其满足堆定义
for (int j=arr.length-1;j>0;j--){
temp=arr[j];
arr[j]=arr[0];
arr[0]=temp;
adjustHeap(arr,0,j);
}
System.out.println("数组="+Arrays.toString(arr));
}
总结:
-
将无序序列构成升序的大顶堆
-
将堆顶元素与末尾元素交换,将最大元素放到末尾
-
重新调整结构,使其满足堆定义