沈阳网站建设活动方案,vc 做网站源码,网站建设编码,wordpress 企业网站模板目录 1. 算法介绍
2. 执行流程⭐⭐⭐⭐⭐✔
3. 代码实现
4. 性能分析 1. 算法介绍
堆是一种数据结构#xff0c;可以把堆看成一棵完全二叉树#xff0c;这棵完全二叉树满足#xff1a;任何一个非叶结点的值都不大于(或不小于)其左右孩子结点的值。若父亲大孩子小#x…目录 1. 算法介绍
2. 执行流程⭐⭐⭐⭐⭐✔
3. 代码实现
4. 性能分析 1. 算法介绍
堆是一种数据结构可以把堆看成一棵完全二叉树这棵完全二叉树满足任何一个非叶结点的值都不大于(或不小于)其左右孩子结点的值。若父亲大孩子小则这样的堆叫作大顶堆;若父亲小孩子大则这样的堆叫作小顶堆。
根据堆的定义知道代表堆的这棵完全二叉树的根结点的值是最大(或最小)的因此将一个无序序列调整为一个堆就可以找出这个序列的最大(或最小)值然后将找出的这个值交换到序列的最后(或最前)这样有序序列关键字增加1个无序序列中关键字减少1个对新的无序序列重复这样的操作就实现了排序。这就是堆排序的思想。
堆排序中最关键的操作是将序列调整为堆。整个排序的过程就是通过不断调整使得不符合堆定义的完全二叉树变为符合堆定义的完全二叉树。 2. 执行流程⭐⭐⭐⭐⭐✔
建堆是先从自下而上从右往左建
初始堆的每一个结点都要满足堆的定义也就是父节点的值大于左右孩子结点的值
选出最大值是将根结点和最后一个结点互换然后继续构建大顶堆
⭐⭐⭐堆顶和最后一个元素交换才算一趟也是该趟的最终序列结果
建堆和排序结果是两个阶段但同属于一趟中。
图示如下 3. 代码实现
为了三个步骤
步骤一先建堆大根堆或者小根堆
步骤二交完堆顶和最后一个元素然后堆的大小减一
步骤三向下调整堆
步骤一只需实现一次步骤二和步骤三循环执行得到最终的有序序列。 //开始排序堆排序分为三个功能 ①开始建堆②交换③向下调整重复②和③步public static void heapSort(int[] array,int len){int end len - 1;//确定最后一个结点的下标createHeap(array);//建堆//当只剩下一个结点的时候就不需要交换while(end 0){//交换swap(array,0,end);//向下调整shiftDown(array,0,end);//调整完一个结点下一个end--;}}//交换数据public static void swap(int[] array,int i,int j){int tmp array[i];array[i] array[j];array[j] tmp;}//堆排序大根堆//从上往下建堆所以先找父节点再找孩子结点public static void createHeap(int[] array){for(int parent (array.length - 1 - 1) / 2;parent 0;parent--){shiftDown(array,parent,array.length);}}//向下调整public static void shiftDown(int[] array,int parent,int len){//定义一个记录孩子下标的变量左孩子int child 2 * parent 1;//判断父节点和孩子结点的大小至少左孩子要存在while(child len){//比较左右孩子if((child 1) len array[child] array[child 1]){child;}//判断父节点和孩子节点if(array[child] array[parent]){swap(array,child,parent);parent child;child 2 * parent 1;}else{break;}}}public static void main(String[] args) {int[] a {5,4,3,2,1};Sort.heapSort(a, a.length);for (int x : a) {System.out.print(x );}} 4. 性能分析
时间辅助度空间复杂度O(N*logN)O(1)数据不敏感数据不敏感
稳定性不稳定。
来上解析怎么计算这个时间复杂度。
1步骤一的时间复杂度首先知道有N个结点开始建堆这个时间复杂度就是O(N)大家可以去看看这篇文章里面有讲建堆的时间复杂度。链接如下
数据结构——堆、堆排序和优先级队列代码为Java版本
2步骤二和步骤三循环的时间复杂度那么我第一个结点交换时需要向下调整为log(N - 1)层交换第二个结点后需要向下log(N - 2)接下来就是log(N - 3)log(N - 4)……log1。所以总的调整次数是log(N - 1) log(N - 2) log(N - 3) log(N - 4) …… log1 log((N - 1)!)。
我们可以在网上看到堆排序的时间复杂度是O(N*logN)这是堆排序的大致估算我们算时间复杂度都是算个大概其实log((N - 1)!) 约等于 NlogN。下面是我的证明结果
① 使用夹逼准则证明
先求上限
再求下限:
因为
所以
当 时
② 则有 ③结论 既是 的低阶函数又是 的高阶函数因此是 的同阶函数
3由于上面的证明步骤我们可以知道堆排序的时间复杂度是 。
