public class HeapSort {
/**
* 采用最大堆升序排序数组
* @param array 已经构建好但未排序的二叉堆数组
* @param border 数组边界,此边界指向最想最后一个“删除”的数据
*(即在数组中最左侧的“删除”数据)。初始值为数组的长度length。
*/
public static void heapSort(int[] array,int border){
int n = 1;
while (border > 0){
//”删除“数组首元素
int temp = array[0];
//--border:border的初始值为数组的长度length,因此先--,再赋值。
// 不能使用border--,否则会下标越界错误。
// 或者采用border=array.length-1,则此处改为border--
array[0] = array[--border];
array[border] = temp;
//调整二叉堆
System.out.println("---------------------第" + n + "次构建二叉堆---------------------");
System.out.println(Arrays.toString(array));
System.out.println("---------------------调整二叉堆--------------------------");
downAdjust(array,border);
System.out.println("-------------------第" + n++ + "次构建二叉堆结束-------------------\n");
}
}
/**
* 下沉调整
* @param array 待调整数组
* @param border 数组边界,此边界指向最想最后一个“删除”的数据(即在数组中最左侧的“删除”数据)
*/
private static void downAdjust(int[] array,int border){
int parentIndex = 0;
int temp = array[parentIndex];
int childIndex = 2*parentIndex + 1;
while (childIndex < border){
//父节点小于或等于子节点,且右子节点大于左子节点,子节点下标定位到右子节点
if (childIndex + 1 < border && array[childIndex] < array[childIndex + 1]){
++childIndex;
}
//父节点大于子节点,直接退出循环。注意:这里只能用temp,而不是array[parentIndex]。
// 因为采用的是单向覆盖,所以array[parentIndex]实际上还是原先的array[childIndex],
// 而逻辑上array[parentIndex]应该是被temp存储的值所覆盖的
if (temp > array[childIndex]){
break;
}
//下沉,子节点单向覆盖父节点
array[parentIndex] = array[childIndex];
//更新父节点和子节点下标
parentIndex = childIndex;
childIndex = 2*parentIndex + 1;
System.out.println(Arrays.toString(array));
}
//最初父节点的值,覆盖其调整后的实际位置
array[parentIndex] = temp;
}
public static void main(String[] args) {
//array为构建好的最大堆。使用无序数组时,需要调用构建二叉堆的方法,将无序数组构建成最大堆
int[] array = new int[]{10,8,9,7,5,4,6,3,2};
heapSort(array,array.length);
System.out.println(Arrays.toString(array));
}
}
---------------------第1次构建二叉堆---------------------
[2, 8, 9, 7, 5, 4, 6, 3, 10]
---------------------调整二叉堆-------------------------
[9, 8, 9, 7, 5, 4, 6, 3, 10]
[9, 8, 6, 7, 5, 4, 6, 3, 10]
-------------------第1次构建二叉堆结束-------------------
---------------------第2次构建二叉堆---------------------
[3, 8, 6, 7, 5, 4, 2, 9, 10]
---------------------调整二叉堆-------------------------
[8, 8, 6, 7, 5, 4, 2, 9, 10]
[8, 7, 6, 7, 5, 4, 2, 9, 10]
-------------------第2次构建二叉堆结束-------------------
---------------------第3次构建二叉堆---------------------
[2, 7, 6, 3, 5, 4, 8, 9, 10]
---------------------调整二叉堆-------------------------
[7, 7, 6, 3, 5, 4, 8, 9, 10]
[7, 5, 6, 3, 5, 4, 8, 9, 10]
-------------------第3次构建二叉堆结束-------------------
---------------------第4次构建二叉堆---------------------
[4, 5, 6, 3, 2, 7, 8, 9, 10]
---------------------调整二叉堆-------------------------
[6, 5, 6, 3, 2, 7, 8, 9, 10]
-------------------第4次构建二叉堆结束-------------------
---------------------第5次构建二叉堆---------------------
[2, 5, 4, 3, 6, 7, 8, 9, 10]
---------------------调整二叉堆-------------------------
[5, 5, 4, 3, 6, 7, 8, 9, 10]
[5, 3, 4, 3, 6, 7, 8, 9, 10]
-------------------第5次构建二叉堆结束-------------------
---------------------第6次构建二叉堆---------------------
[2, 3, 4, 5, 6, 7, 8, 9, 10]
---------------------调整二叉堆-------------------------
[4, 3, 4, 5, 6, 7, 8, 9, 10]
-------------------第6次构建二叉堆结束-------------------
---------------------第7次构建二叉堆---------------------
[2, 3, 4, 5, 6, 7, 8, 9, 10]
---------------------调整二叉堆-------------------------
[3, 3, 4, 5, 6, 7, 8, 9, 10]
-------------------第7次构建二叉堆结束-------------------
---------------------第8次构建二叉堆---------------------
[2, 3, 4, 5, 6, 7, 8, 9, 10]
---------------------调整二叉堆-------------------------
-------------------第8次构建二叉堆结束-------------------
---------------------第9次构建二叉堆---------------------
[2, 3, 4, 5, 6, 7, 8, 9, 10]
---------------------调整二叉堆-------------------------
-------------------第9次构建二叉堆结束-------------------
[2, 3, 4, 5, 6, 7, 8, 9, 10]