做网站是什么专业,企业网站建设的实验报告,要压实互联网企业的什么责任,2022年新闻摘抄十条简短文章目录 前言1. 堆排序1.1 堆排序的思想1.2 堆排序的实现 2. 为什么向下调整而不是向上调整 前言 本章主要会讲堆排序的实现过程以及向上调整和向下调整的时间复杂度#xff0c;在学习本章前#xff0c;需要对堆、以及向上调整和向下调整有一个了解#xff0c;如果不了解的… 文章目录 前言1. 堆排序1.1 堆排序的思想1.2 堆排序的实现 2. 为什么向下调整而不是向上调整 前言 本章主要会讲堆排序的实现过程以及向上调整和向下调整的时间复杂度在学习本章前需要对堆、以及向上调整和向下调整有一个了解如果不了解的话可以先看看这篇文章《堆的实现及TOP-K问题》 1. 堆排序 1.1 堆排序的思想
堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。
这里以升序为例我们通过一个向下调整的算法建一个大堆然后将第一个数据和最后一个数据交换一下以此类推把大的数往后面放。 1.2 堆排序的实现 堆排序使用堆来选数效率就高了很多。时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定
我们用代码来实现一下它的逻辑
// 向下调整
void AdjustDown(int* a, int size, int parent) // 建大堆
{int child parent * 2 1; // 左孩子while (child size){// 判断左孩子和右孩子哪个大,就令child等于哪个孩子if (child 1 size a[child] a[child 1]) {child;}if (a[parent] a[child]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}elsebreak; // 如果父亲和孩子不用交换,就代表已经排好了,不需要再往后比较}
}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; // 调整end的位置}
}2. 为什么向下调整而不是向上调整 上面堆排序的时候不论是建堆还是排序的时候使用的是向下调整的算法那么为什么不用向上调整的算法呢
在这里我们先来看一下向下调整算法 再来看看向上调整算法 很明显我们可以看出向下调整的时间复杂度是要比向上调整算法的时间复杂度低的所以我们只要掌握住向下调整算法就可以了向上调整算法就当做个了解。
