逻辑
堆是一种所有父节点都大于等于(大根堆)或小于等于(小根堆)其子节点的完全二叉树。堆排序(升序)就是一种将数组视为一个完全二叉树,将其变为一个大根堆后将堆顶放到数组尾,重复n次后数组有序的排列方法,时间复杂度为O(nlogn)。(感觉好像冒泡哦)
简述:将数组视为完全二叉树,将其变为堆后将堆顶置底,重复n次。
代码
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int arr[] = {4, 6, 8, 5, 9 , 7, 1, 3, 2};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int arr[]){
for(int i = arr.length/2-1;i>=0;i--){
heapAdjust(arr,i,arr.length);
}
int temp;
for(int i = arr.length-1;i>0;i--){
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapAdjust(arr,0,i);
}
}
public static void heapAdjust(int arr[], int start, int end){
int temp = arr[start];
for(int i = start * 2 + 1;i < end;i = i * 2 + 1){
if (i+1 < end && arr[i] < arr[i+1]) i++;
if (temp < arr[i]){
arr[start] = arr[i];
start = i;
}else break;
}
arr[start] = temp;
}
}
标签:arr,蒜法,Java,temp,int,堆排序,start,二叉树,public
From: https://blog.csdn.net/fanqieyuu/article/details/141222853