三合一网站建设系统,企业营销策划及推广,网站建设课程设计实训总结,营销型网站建设公司哪里有目录#xff1a; 1:如何建堆(两种方法) 2:两种方法建堆的时间复杂度分析与计算 3:不同类型的排序方式我们应该如何建堆 文章正式开始#xff1a; 1#xff1a;如何建堆 在实现堆排序之前我们必须得建堆#xff0c;才能够实现堆排序 首先在讲解如何建堆之前让我们先来回顾一…目录 1:如何建堆(两种方法) 2:两种方法建堆的时间复杂度分析与计算 3:不同类型的排序方式我们应该如何建堆 文章正式开始 1如何建堆 在实现堆排序之前我们必须得建堆才能够实现堆排序 首先在讲解如何建堆之前让我们先来回顾一下堆的概念堆是一种完全二叉树它有两种形式一种是大根堆另外一种是小根堆。 大根堆所有的父亲结点大于或等于孩子结点。 小根堆所有的父亲结点小于或等于孩子结点。 本文在介绍堆排序的时候我们都默认排升序。 方法1我们采用向上调整算法建堆 我们知道向上调整算法的前提是前面的数必须是堆所以我们就形成了一种思路 第一个数我们可以看成是一个堆那么从第二个数开始我们就依次采用向上调整算法这样最后我们的数字就会形成一个堆。 图解 向上调整建堆的代码如下如果不理解可以自己尝试画图 //假设排升序建大堆
void HeapSort(int* a, int n){//先建堆,用向上调整算法for (int i 1; i n; i){AdjustUp(a, i);}} 方法2采用向下调整的思路建堆 向下调整的前提要调整的对象左右子树都得是堆 那么我们如何通过一个数组来原地建堆呢 其实我们可以这样想叶子结点既可以看作是大堆也可以看作是小堆所以我们可以从后面往前面来建堆。 思路找到倒数第一个非叶子结点这样我们可以保证左右子树都是堆才能够对整个堆使用向下调整算法的思想。 那么最后一个非叶子结点如何才能找到呢这里不就是我们要记住的一个特点吗通过孩子结点来算父亲结点。 parent(child-1)/2; 我们先找到最后一个结点的下标然后通过结点算父亲的公式不就可以算出来了吗 所以倒数第一个非叶子结点的下标不就是 (n-1-1)/2吗 图解过程 2:两种方法建堆复杂度的分析 首先我们直接公布结论 向上调整算法的时间复杂度为O(N*logN),向下调整算法的时间复杂度为O(N),所以建堆在复杂度的层面来说向下调整算法是优于向上调整算法的。 向上调整算法的时间复杂度分析 我们知道向上调整算法是依次将后一个元素向上进行调整那么最坏的情况下就是我们所插入一个数就要调整到根节点处。 同理向下调整的复杂度分析 为啥同样都是建堆的过程可是为啥向下调整算法的时间复杂度优于向上调整算法呢 因为向下调整算法时最后一层结点不需要向下调整且最后一层的结点比较多从下往上结点个数变少乘以的层数变多但是主要取决于时间复杂度的是结点个数多的。 而向上调整算法最后一层结点的个数多且需要调整的层数也最高导致向上调整的时间复杂度高。 3.堆排序 在讲了前面两种算法的基础上我们就可以来谈一谈我们的堆排序了堆排序并不是我们所讲的数据结构虽然说堆数据结构也可以看出堆的升序与降序但是我们可能并不是只要打印这个数组出来我们可能还会进行一些算法比如2分查找....。 堆排序的思路 1首先对数组进行建堆。 2将最后一个元素与第一个元素交换在向下进行调整 3循环往复的进行最后排除来的就是我们所需要的结果了。 那我们在排升序的时候应该见建大堆还是小堆呢? 相信许多人在看到要排升序的时候可能第一反应的是建小堆因为小堆中的第一个数是所有元素中最小的那个数但是当我们建立小堆的时候那我们的第二个小的数字如何取呢 且当我们将第一个元素排好之后后面的元素的关系都不对了就会形成兄弟变父子父子叔侄变兄弟那么我们可能还需要建一次堆那么总体的时间复杂度为N*(N*logN), 所以我们排升序需要建大堆排降序需要建小堆。 而我们为什么可以这样子做呢 我们假设有一个数组我们已近将他建成大堆了那么我们很明显知道根节点最大那么我们就可以这样子做。 将最大的根结点与最后一个数字进行交换由于我们只是交换了根结点与最后一个元素其他的结构没有动所以就可以使用向下调整然后在对前n-1个元素进行向下调整整个的时间复杂度为logn。每次选一个大的我们向将大的排在最后循环进行就可以排成我们所需要的结果了。 代码实现
void HeapSort(int* a, int n)
{//向下调整算法建堆,建大堆排升序for (int i (n-1-1)/2; i 0; i--){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}
} 也可以使用向上调整建堆进行堆排序 假设排升序建大堆
//void HeapSort(int* a, int n)
//{
// //先建堆,用向上调整算法
// for (int i 1; i n; i)
// {
// AdjustUp(a, i);
// }
//
// //将最后一个数与根节点交换
// //在进行向下调整循环执行
// int end n - 1;
// /*while (end 0)
// {
// Swap(a[end], a[0]);
// AdjustDown(a, end, 0);
// --end;
// }*/
//
//
//
//
//} 本章完 感谢观看。
