陕西建设厅八大员官方网站,wordpress汇聚素材网,安徽建工网,新手小白如何互联网创业目录堆排序概述代码实现时间复杂度堆排序概述
堆排序#xff08;Heap Sort#xff09;是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构#xff0c;每个结点的值都大于或等于其左右孩子结点的值#xff0c;称为大顶堆#xff1b;或者每个结点…
目录堆排序概述代码实现时间复杂度堆排序概述
堆排序Heap Sort是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构每个结点的值都大于或等于其左右孩子结点的值称为大顶堆或者每个结点的值都小于或等于其左右孩子结点的值称为小顶堆。如下图
同时我们对堆中的结点按层进行编号将这种逻辑结构映射到数组中就是下面这个样子 该数组从逻辑上讲就是一个堆结构我们用简单的公式来描述一下堆的定义就是 大顶堆arr[i] arr[2i1] arr[i] arr[2i2] 小顶堆arr[i] arr[2i1] arr[i] arr[2i2]
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆一般升序采用大顶堆降序采用小顶堆)
1假设给定无序序列结构如下 2此时我们从最后一个非叶子结点开始叶结点自然不用调整第一个非叶子结点 arr.length/2-15/2-11也就是下面的6结点从左至右从下至上进行调整 3找到第二个非叶节点4由于[4,9,8]中9元素最大4和9交换 4这时交换导致了子根[4,5,6]结构混乱继续调整[4,5,6]中6最大交换4和6。 此时我们就将一个无需序列构造成了一个大顶堆
步骤二 将堆顶元素与末尾元素进行交换使末尾元素最大。然后继续调整堆再将堆顶元素与末尾元素交换得到第二大元素。如此反复进行交换、重建、交换
1将堆顶元素9和末尾元素4进行交换9就不用继续排序了 2重新调整结构使其继续构建大顶堆9除外 3再将堆顶元素8与末尾元素5进行交换得到第二大元素8. 步骤三 后续过程继续进行调整交换如此反复进行最终使得整个序列有序
排序思路 将无需序列构建成一个堆根据升序降序需求选择大顶堆或小顶堆; 将堆顶元素与末尾元素交换将最大元素沉到数组末端; 重新调整结构使其满足堆定义然后继续交换堆顶元素与当前末尾元素反复执行调整交换步骤直到整个序列有序
动图展示 代码实现
import java.util.Arrays;public class HeapSort {public static void main(String[] args) {int[] arr {4, 6, 8, 5, 9};heapSort(arr);
// [4, 6, 8, 5, 9]
// [4, 9, 8, 5, 6]
// [4, 9, 8, 5, 6]
// [9, 6, 8, 5, 4]
// [9, 6, 8, 5, 4]
// [9, 6, 8, 5, 4]
// [8, 6, 4, 5, 9]
// [8, 6, 4, 5, 9]
// [6, 5, 4, 8, 9]
// [6, 5, 4, 8, 9]
// [5, 4, 6, 8, 9]
// [5, 4, 6, 8, 9]
// [4, 5, 6, 8, 9]}//堆排序public static void heapSort(int[] arr) {//开始位置是最后一个非叶子节点最后一个节点的父节点int start (arr.length - 1) / 2;//循环调整为大顶堆for (int i start; i 0; i--) {maxHeap(arr, arr.length, i);}//先把数组中第0个和堆中最后一个交换位置for (int i arr.length - 1; i 0; i--) {int temp arr[0];arr[0] arr[i];arr[i] temp;//再把前面的处理为大顶堆maxHeap(arr, i, 0);}}//数组转大顶堆,size:调整多少从最后一个向前减index:调整哪一个最后一个非叶子节点public static void maxHeap(int[] arr, int size, int index) {//左子节点int leftNode 2 * index 1;//右子节点int rightNode 2 * index 2;//先设当前为最大节点int max index;//和两个子节点分别对比找出最大的节点if (leftNode size arr[leftNode] arr[max]) {max leftNode;}if (rightNode size arr[rightNode] arr[max]) {max rightNode;}//交换位置if (max ! index) {int temp arr[index];arr[index] arr[max];arr[max] temp;//交换位置后可能会破坏之前排好的堆所以之间排好的堆需要重新调整maxHeap(arr, size, max);}//打印每次排序后的结果System.out.println(Arrays.toString(arr));}
}时间复杂度
最优时间复杂度o(nlogn)最坏时间复杂度o(nlogn)稳定性不稳定
它的运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。
在构建堆的过程中因为我们是完全二叉树从最下层最右边的非终端结点开始构建将它与其孩子进行比较和若有必要的互换对于每个非终端结点来说其实最多进行两次比较和互换操作因此整个构建堆的时间复杂度为O(n)。
在正式排序时第i次取堆顶记录重建堆需要用O(logi)的时间完全二叉树的某个结点到根结点的距离为log2i1并且需要取n-1次堆顶记录因此重建堆的时间复杂度为O(nlogn)。
所以总体来说堆排序的时间复杂度为O(nlogn)。由于堆排序对原始记录的排序状态并不敏感因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。这在性能上显然要远远好过于冒泡、简单选择、直接插入的O(n2)的时间复杂度了。
空间复杂度上它只有一个用来交换的暂存单元也非常的不错。不过由于记录的比较与交换是跳跃式进行因此堆排序是一种不稳定的排序方法。
