三沙网站建设,商业网站的特点,html主页设计,centos7 wordpress无权限章节目录#xff1a;一、相关概述1.1 基本介绍1.2 排序思想二、基本应用2.1 步骤说明2.2 代码示例三、结束语一、相关概述
1.1 基本介绍
堆排序是利用堆这种数据结构而设计的一种排序算法#xff0c;堆排序是一种选择排序。它的最坏最好平均时间复杂度均为 O(nlogn)#x…
章节目录一、相关概述1.1 基本介绍1.2 排序思想二、基本应用2.1 步骤说明2.2 代码示例三、结束语一、相关概述
1.1 基本介绍
堆排序是利用堆这种数据结构而设计的一种排序算法堆排序是一种选择排序。它的最坏最好平均时间复杂度均为 O(nlogn)它属于不稳定排序即在排序过程中如果两个键的值相同那么他们的相对位置会发生变化。堆是具有以下性质的完全二叉树每个节点的值都大于或等于其左右孩子节点的值称为大顶堆每个节点的值都小于或等于其左右孩子节点的值称为小顶堆。注意 : 没有要求节点的左孩子的值和右孩子的值的大小关系。大顶堆示意图 小顶堆示意图 说明一般升序采用大顶堆降序采用小顶堆。
1.2 排序思想
将待排序序列构造成一个大顶堆此时整个序列的最大值就是堆顶的根节点创建一个堆 H[0……n-1]将其与末尾元素进行交换此时末尾就为最大值把堆首最大值和堆尾互换然后将剩余 n-1 个元素重新构造成一个堆这样会得到 n 个元素的次小值把堆的尺寸缩小 1目的是把新的数组顶端数据调整到相应位置如此反复执行元素的个数逐渐减少便能得到一个有序序列了重复步骤 2直到堆的尺寸为 1。
二、基本应用
2.1 步骤说明 需求假设将数组 {4,6,8,5,9} 要求使用堆排序法将数组升序排序。 示意图 2.2 代码示例
public class HeapSort {public static void main(String[] args) {int[] array new int[10];for (int i 0; i array.length; i) {// 随机 100 以内的整数。array[i] (int) (Math.random() * 100);}System.out.println(before: Arrays.toString(array));// before:[72, 36, 54, 10, 87, 11, 2, 81, 81, 20]heapSort(array);System.out.println(after: Arrays.toString(array));// after:[2, 10, 11, 20, 36, 54, 72, 81, 81, 87]}/*** 堆排序。** param array 数组*/public static void heapSort(int[] array) {// 将无序序列构建成一个堆 (升序选择大顶堆 / 降序选择小顶堆)。for (int i (array.length / 2 - 1); i 0; i--) {adjustHeap(array, i, array.length);}// 将堆顶元素与末尾元素交换并反复调整结构。int temp;for (int j (array.length - 1); j 0; j--) {// 交换。temp array[j];array[j] array[0];array[0] temp;adjustHeap(array, 0, j);}}/*** 将一个数组(二叉树)调整成一个大顶堆。** param array 待调整的数组* param index 非叶子节点在数组中的索引* param length 对多少个元素继续调整 (该值不断减小)*/public static void adjustHeap(int[] array, int index, int length) {// 将当前元素值保存至临时变量。int temp array[index];// 开始调整动作// ( k i * 2 1 ) : 表示 k 是 index 节点的左子节点。for (int k (index * 2 1); k length; k (k * 2 1)) {// 说明左子节点的值小于右子节点的值。if ((k 1 length) (array[k] array[k 1])) {// 指向右子节点。k;}// 如果子节点大于父节点。if (array[k] temp) {// 则把较大值赋值给当前节点。array[index] array[k];// 索引指向k继续循环比较。index k;} else {break;}}// 循环结束表示已经 index 已经为父节点树的最大值。即最顶部array[index] temp;}
}三、结束语 “-------怕什么真理无穷,进一寸有一寸的欢喜。” 微信公众号搜索饺子泡牛奶。
