堆排序
代码:
public static void heapSort(int [] arr) {
for(int i = 0; i < arr.length; i++) {
// 每次建堆都能找出最大的一个元素,并将它与最后一个元素交换
// 同时排除最后一个元素,这样就定位了一个元素的位置,以此类推
maxHeap(arr, arr.length - i);
swap(arr,0,arr.length - i - 1);
}
}
// 从数组的最后一个元素开始构建
public static void maxHeap(int[] arr,int size) {
// 从数组末尾开始构建(没有子节点的话也就不需要构建 所以这里从size/2开始构建),直到第一个元素
// 这样才保证构建出来的大根堆的根节点就是最大的
for(int i = size / 2; i >= 0; i--) {
buildHeap(arr, i, size);
}
}
// 建堆
public static void buildHeap(int[] arr,int currendRootNode,int size) {
if(currendRootNode < size) {
// 左孩子
int left=currendRootNode * 2 + 1;
// 右孩子
int right=currendRootNode * 2 + 2;
// 将当前节点看成是最大的节点
int max = currendRootNode;
if(left < size) {
// 如果左孩子比根元素要大,记录其位置
if(arr[left] > arr[max]) {
max = left;
}
}
if(right < size) {
// 如果右孩子比根元素要大,记录其位置
if(arr[right] > arr[max]) {
max = right;
}
}
// 如果最大的不是根元素,那么就交换
if(max!=currendRootNode) {
swap(arr,max,currendRootNode);
// 继续往下比较
buildHeap(arr,max,size);
}
}
}
public static void swap(int[] arr,int x,int y) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
今天Jacky真好看