废话不多说,直接上代码,注释都在代码中,利用大顶堆排序(最终数组从小到大),复制即用无需导包
package 大顶堆;
import java.lang.reflect.Array;
import java.util.Arrays;
public class HeapSort {
public static void sort(int[] source){
// 第一步: 构建堆,数组下标0不存储
int[] heap = new int[source.length + 1];
// 步骤二:待排序数组,构建一个无序堆
System.arraycopy(source, 0, heap, 1, source.length);
// 步骤三:堆中元素下沉操作, 长度的一半开始,因为堆的特性,有一半都是叶子节点,叶子之间不需要比较
// 此处构建出来一个标准大顶堆,大顶堆中的数组其实是无序的
for(int i = heap.length / 2; i > 0; i--){
down(heap, i, heap.length - 1);
}
System.out.println("大顶堆: " + Arrays.toString(heap));
// 步骤四:堆排序
// 记录最大需要排序的索引下标, 因为每一次排序,最后一个都不需要进行比较,因为每一次都会排好一个,而这个会沉到最后
// 而第一次排序时,所以元素都要进行排序比较,所以需要排序的个数 以及 下标,就是source.length - 1就是全要参与比较
int maxUnSortIndex = source.length - 1;
// 循环排序,当排到只剩最后一个时就不用排了
// 这里为什么还要排序? 因为上面排好的大顶堆中数组是无序的,而我们要的是数组是有序的,所以下面代码就相当于循环获取大顶堆中的元素。
// 而按照大顶堆取法来说,最上面元素一定是最大的
// 第一次循环之后,最大值会落到最后一个节点,即数组最后一个
// 第二次循环,新的最大值(第二大的值)就会落到倒数第二个节点
// 第三次循环如此往复,就会按照从小到大的顺序排好
while (maxUnSortIndex != 1){
// 交换位置,由于是大顶堆,所以把最后一个要排序的节点和第一个交换,然后下沉,从第一个开始下沉
// 因为大顶堆是大的值在最上面,而我们要的是从小打到排序,所以交换位置后,最大值会落到本次循环总节点数的最后一个节点上,即最大值沉到了最后
swap(heap, 1, maxUnSortIndex);
// 每次下沉完毕,本次最后一个元素就排好了,所以要maxUnSortIndex-1个,下次排序循环就不带这个排好的元素了,所以需要排序的元素个数就要-1
// 减1后,下次循环就会把第二个最大值落到倒数第二个子节点的位置
maxUnSortIndex--;
// 继续堆堆顶元素进行下沉,重新堆化,把新的最大值再次放到最上面,然后供下次循环获取
down(heap, 1, maxUnSortIndex);
}
// 把heap中排好序的数组复制到原始数组中
System.arraycopy(heap, 1, source, 0, source.length);
}
/**
* 堆排序下沉
* @param heap 堆数组
* @param k 下标
* @param range 数组元素总个数
*/
private static void down(int[] heap, int k, int range) {
// 存在子节点时再进行while循环
while (2 * k < range){
// 存储左右子节点大的那个值的【下标】
int maxValue;
// 判断是否存在右节点
if(2 * k + 1 < range){
// 比较左右节点大小,【假设左为父,右为子】
if(childBig(heap, 2 * k, 2 * k + 1)){
// 右节点大
maxValue = 2 * k + 1;
}else{
// 左节点大
maxValue = 2 * k;
}
}else{
// 不存在右子节点,则左节点就是大的值
maxValue = 2 * k;
}
// 把当前k节点和较大的子节点比较
if(childBig(heap, k, maxValue)){
// 子节点大则交换父子节点位置
swap(heap, k, maxValue);
// 当前节点要下沉一层,则节点下标要更改为子节点的,然后循环继续和孙子节点比较
k = maxValue;
}else{
// 子节点小,则不用再比较了,孙子节点一定更小,直接中断循环
break;
}
}
}
/**
* 比较父子节点大小大小, item[parent]的元素是否小于item[child]元素的大小
*
* 这里要多一个heap, 以内之前的大顶堆items是本身类中的,而堆排序是传进来的数组,不带上不行
*/
public static boolean childBig(int[] heap, int parent, int child){
// 如果父节点 < 子节点,则返回true,表示需要交换
return heap[parent] < heap[child];
}
/**
* 交换父子节点元素位置
* @param heap
* @param parent
* @param child
*/
public static void swap(int[] heap, int parent, int child){
int temp = heap[parent];
heap[parent] = heap[child];
heap[child] = temp;
}
}