整站seo排名外包,中国农业科技推广网,搭建网站的流程,高仿卡西欧手表网站文章目录 #x1f412;个人主页#x1f3c5;算法思维框架#x1f4d6;前言#xff1a; #x1f380;堆排序 时间复杂度O(n*logn)#x1f387;1. 算法步骤思想#x1f387;2、动画演示#x1f387;3.代码实现 #x1f412;个人主页 #x1f3c5;算法思维框架 #x1… 文章目录 个人主页算法思维框架前言 堆排序 时间复杂度O(n*logn)1. 算法步骤思想2、动画演示3.代码实现 个人主页 算法思维框架 前言
本篇博客主要以介绍十大排序算法中的堆排序有详细的图解、动画演示、良好的代码注释帮助加深对这些算法的理解进行查漏补缺~
堆排序 时间复杂度O(n*logn) 堆排序Heapsort 是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法 大顶堆每个节点的值都大于或等于其子节点的值在堆排序算法中用于升序排列 小顶堆每个节点的值都小于或等于其子节点的值在堆排序算法中用于降序排列 堆排序的平均时间复杂度为 Ο(nlogn)。 有好多人都说堆排序代码有点复杂但是它的思路其实是最好理解的他的思路是将大根堆顶的最大值元素放到数组没有排序区间的末尾然后对没有排序的区间重新变成大根堆直到没有排序的区间中只剩一个元素就排好序了。 难的无非是不会将一个数组变成堆heapify也不会取出堆顶元素后删除操作(下沉操作)再将其变成堆。
1. 算法步骤思想 创建一个堆 H[0……n-1] 【heapify()操作-----时间复杂度O(n)】把堆首最大值和堆尾互换【交换数组中的堆顶与数组未排序区间的末尾元素】调用swim()方法-----时间复杂度O(logn)使除过堆尾元素的树满足最大堆的性质【对没有排序的区间进行下沉操作重新生成堆】重复步骤 2直到堆中只有一个元素。 2、动画演示 3.代码实现
public int[] sort(int[] nums) {if(numsnull||nums.length2){return nums;}//思路【堆排序】先将nums[]构建成大根堆heapify()操作,// 再将堆顶元素与未排序区间的末尾元素进行交换对此时的堆顶元素进行【无序区间】的下沉操作重复上述操作....直至数组有序heapify(nums);//【将nums[]数组变成堆】//进行排序for (int i nums.length-1; i 0; i--) {//交换int tempnums[i];nums[i]nums[0];nums[0]temp;//对根节点进下沉操作让没有排序的区间重新变成堆swim(nums,0,i);}return nums;}//写两个辅助方法获取父亲节点下标获取左孩子节点下标private int getParentIndex(int childIndex){return (childIndex-1)/2;}private int getLeftChildIndex(int parentIndex){return 2*parentIndex1;}private void heapify(int[] nums){//【将nums[]数组变成堆】//思路拿到数组最后一个元素的父亲节点下标直到根节点依次进行下沉操作int lastParentIndexgetParentIndex(nums.length-1);for (int i lastParentIndex; i 0 ; i--) {swim(nums,i,nums.length);}}/*** 下沉操作* param nums 进行下沉操作的数组* param index 需要进行下沉操作的节点* param length 进行下沉操作的区间长度*/private void swim(int[] nums,int index,int length){//下沉思路将目标值rootVal与当前节点index的左右孩子最大优先级进行比较// 1.如果rootVal孩子优先级,孩子优先级覆盖当前父亲节点index,index索引最大优先级的孩子重新找孩子进行比较// 2.如果rootVal孩子优先级找到了break,将当前节点nums[index]rootVal//3.如果找到头都没有找到将当前节点nums[index]rootVal 【情况2、3可合并处理】int rootValnums[index];//寄存将要下沉节点的值int leftIndexgetLeftChildIndex(index);//获取当前节点的左孩子int maxChildPiroirtyIndexleftIndex;//【默认左孩子为孩子的最大优先级原因堆是一棵完全二叉树...】while (leftIndexlength){//左孩子存在int rightIndexleftIndex1;//右孩子下标if(rightIndexlengthnums[leftIndex]nums[rightIndex]){//左孩子存在且左孩子优先级右孩子优先级maxChildPiroirtyIndexrightIndex;}//进行优先级的比较if(rootValnums[maxChildPiroirtyIndex]){nums[index]nums[maxChildPiroirtyIndex];//覆盖父节点//更新索引指向indexmaxChildPiroirtyIndex;leftIndexgetLeftChildIndex(index);maxChildPiroirtyIndexleftIndex;}else {break;}}nums[index]rootVal;//插入目标值}
