做网站合伙怎么分,织梦和wordpress能共存,c s网站开发模式,公司网站怎么做关键字文章目录 一、堆排序思想二、向上调整建堆排序三、向下调整建堆排序四、总结 对于什么是堆#xff0c;堆的概念分类以及堆的向上和向下两种调整算法可见#xff1a;
堆的创建 一、堆排序思想
int a[] { 2,3,5,7,4,6 };对于这样一个数组来说#xff0c;要想要用堆排序对它… 文章目录 一、堆排序思想二、向上调整建堆排序三、向下调整建堆排序四、总结 对于什么是堆堆的概念分类以及堆的向上和向下两种调整算法可见
堆的创建 一、堆排序思想
int a[] { 2,3,5,7,4,6 };对于这样一个数组来说要想要用堆排序对它进行排序首先要做的就是用数组里的数据建立一个堆大堆和小堆都可以只有是一个堆才能使用堆排序。
那么应该建大堆还是小堆呢例如对于这个数组要排升序如果建立小堆的话
建成小堆后找出了最小的元素要找到次小的就需要把剩下的元素看作堆但剩下的元素不一定是堆需要重新建堆代价比较大。
更好的方法是升序建立大堆堆顶和最后一个元素交换最后一个最大的元素就已经有序对剩下数据进行向下调整就能找出第二大的以此就能将数组排好序。 总结一下堆排序的思想就是 1、根据要排什么序建大堆或小堆此时堆顶端的元素就是最值 2、将顶端元素和末尾元素交换此时末尾元素就是有序的剩下的还有n-1个元素 3、将剩下的n-1个元素再次构建成堆然后将堆顶端元素与第n-1个元素互换反复执行便可得到有序数组 升序建大堆 降序建小堆
二、向上调整建堆排序
使用向上调整算法建堆的堆排序
例如将数组a用堆排序按从小到大排列升序 首先利用向上调整算法建大堆此方法可参考堆的创建
向上调整算法的前提条件是前面的元素是堆
对于单个结点来说既可以看作一个大堆所以便可以通过向上调整算法依次对数组元素进行调整那进行调整的元素前就一定是堆满足条件 创建好的大堆如下
将堆的顶端元素7和末尾元素2进行交换对除7外剩下的元素进行向下调整重新构建大堆 此时7已经是有序的将元素6和元素3进行交换对除6、7外剩下元素进行向下调整重新构建大堆 此时6、7已经有序将元素5和元素2进行交换对除5、6、7外剩下元素进行向下调整重新构建大堆 此时5、6、7已经有序将元素4和元素2进行交换此时数组已经有序 排序完数组a变为
用向上调整算法建堆的升序的堆排序代码如下
#includestdio.h
#includestdlib.h
#includestdbool.h
typedef int HPDataType;
//交换结点的函数
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}
//向上调整算法(大堆)
void AdjustUp(HPDataType* a, int child)
{//找出双亲的下标int parent (child - 1) / 2;while (child0){//孩子结点比双亲大则交换if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}//向下调整算法(大堆)
void AdjustDown(HPDataType* a, int n, int parent)
{//先默认左孩子是较大的int child parent * 2 1;while (child n){//找出左右孩子中较大的if (child 1 n a[child 1] a[child]){child;}//孩子节点更小则交换if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}
//排序
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[0], a[end]);//对剩余元素进行向下调整AdjustDown(a, end, 0);end--;}
}
int main()
{int a[] { 2,3,5,7,4,6 };HeapSort(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i){printf(%d , a[i]);}return 0;
}运行结果如下
空间复杂度O(1) 平均时间复杂度O(nlogn)
三、向下调整建堆排序
向下调整建堆排序与向上调整建堆排序不同的地方就在于建堆时用的算法不同建好堆之后的后续操作都是相同的。
还是对上面那个案例我们用向下调整算法建堆
向下调整算法前提条件左右子树必须是堆才能调整 对于这个完全二叉树来说它的倒数第一个非叶子节点2的左子树为4没有右子树可以用向下调整再上一个节点6的左右子树是单个节点也可以看作堆所有我们就可以从倒数第一个非叶子节点也就是最后一个节点的父亲开始向下调整 利用向下调整建好堆之后的后续操作与向上调整建好堆之后的操作一样这里就不再演示
用向下调整算法建堆的升序的堆排序代码更改如下
void HeapSort(int* a, int n)
{向上调整建堆//for (int i 1; i n; i)//{// AdjustUp(a, i);//}// //向下调整建堆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--;}
}利用向下调整建堆的堆排序时间复杂度为O(n)比利用向上调整建堆更优
四、总结
使用堆排序需要先建堆建堆有向上调整算法和向下调整算法两种方法但向下调整算法的平均时间复杂度更低建好堆之后便首尾数据互换再对剩下元素重新建堆反复执行便可得到有序数列。
重点知识总结
小堆所有的双亲结点都小于孩子节点根节点最小大堆所有的双亲结点都大于孩子节点根节点最大向下调整算法前提左右子树必须是堆才能调整向上调整算法前提前面的元素是堆堆排序建堆时升序建大堆降序建小堆
