上海建站网,重庆荣昌网站建设,wordpress 中文文件,wordpress是哪个国家的堆排序
1、堆排序原理
堆排序是利用到了堆这种数据结构#xff0c;我们首先回顾一下二叉堆的特性#xff1a;
最大堆的堆顶是整个堆中的最大元素。最小堆的堆顶是整个堆中的最小元素。
以最大堆为例#xff0c;如果删除一个最大堆的堆顶#xff08;并不是完全删除…堆排序
1、堆排序原理
堆排序是利用到了堆这种数据结构我们首先回顾一下二叉堆的特性
最大堆的堆顶是整个堆中的最大元素。最小堆的堆顶是整个堆中的最小元素。
以最大堆为例如果删除一个最大堆的堆顶并不是完全删除而是跟末尾的节点交换位置经过自我调整第2大的元素就会被交换上来成为最大堆的新堆顶。如下图所示 在删除值为10的堆顶节点后经过调整值为9的新节点就会顶替上来在删除值为9的堆顶节点后经过调整值为8的新节点就会顶替上来……
由于二叉堆的这个特性每一次删除旧堆顶调整后的新堆顶都是大小仅次于旧堆顶的节点。那么只要反复删除堆顶反复调整二叉堆所得到的集合就会成为一个有序集合。
而二叉堆实际是存储在数组中的堆排序过后数组中的元素排列如下 综上堆排序的步骤为
把无序数组构建成二叉堆。需要从小到大排序则构建成最大堆需要从大到小排序则构建成最小堆。循环删除堆顶元素替换到二叉堆的末尾调整堆产生新的堆顶。
2、堆排序的代码实现
堆排序的代码如下如下升序排列
/*** “下沉”调整* param array 待调整的堆* param parentIndex 要“下沉”的父节点* param length 堆的有效大小*/
public static void downAdjust(int[] array, int parentIndex,int length) {// temp 保存父节点值用于最后的赋值int temp array[parentIndex];int childIndex 2 * parentIndex 1;while (childIndex length) {// 如果有右孩子且右孩子大于左孩子的值则定位到右孩子if (childIndex 1 length array[childIndex 1] array[childIndex]) {childIndex;}// 如果父节点大于任何一个孩子的值则直接跳出if (temp array[childIndex])break;//无须真正交换单向赋值即可array[parentIndex] array[childIndex];parentIndex childIndex;childIndex 2 * childIndex 1;}array[parentIndex] temp;
}/*** 堆排序升序* param array 待调整的堆*/
public static void heapSort(int[] array) {// 1. 把无序数组构建成最大堆for (int i (array.length-2)/2; i 0; i--) {downAdjust(array, i, array.length);}System.out.println(Arrays.toString(array));// 2. 循环删除堆顶元素移到集合尾部调整堆产生新的堆顶for (int i array.length - 1; i 0; i--) {// 最后1个元素和第1个元素进行交换int temp array[i];array[i] array[0];array[0] temp;// “下沉”调整最大堆downAdjust(array, 0, i);
}
