目录
- 引言
- 堆排序的实现
- **堆的向下调整算法**
- 对排序的时间复杂度
- 建堆的时间复杂度:
- 排序过程的时间复杂度:
- 总体时间复杂度:
引言
堆排序(Heap Sort)是一种基于比较的排序算法,利用堆的数据结构来实现。它的时间复杂度为O(n log n),并且是原地排序算法,不需要额外的存储空间,这使得它在空间复杂度方面具有优势。
堆排序的关键在于构建和维护堆的性质。虽然堆排序的时间复杂度较好,但在实际应用中,由于其不具备插入和删除操作的优势,因此在一些特殊方面很少被选择。
堆排序的实现
堆排序实现的基本思路为:
- 建堆
升序:建大堆
降序:建小堆 - 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整,因此掌握了向下调整,就可以完成堆排序。
堆的向下调整算法
从给出的 一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。
向下调整算法有一个前提:左右子树必须是一个堆,才能调整。
如图:
void Swap(int* a, int* b)
{
int c = *a;
*a = *b;
*b = c;
}
void AdjustDwon(int* 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;
}
}
在一个堆中,根节点从0开始编号,下标为 i(i > 0) 的结点的左右孩子结点及父结点的下标:
左孩子:2i(i>0)
右孩子:2i+1
父节点: (i-1)/2
根据树的父子结点的联系来确定数组下标
void HeapSort(int* a, int n)
{
//起始i用n-1是数组的最后一个为n-1,起始i为最后一个元素的父节点
for (int i = (n - 1 - 1) / 2;i >= 0;i--)
{
AdjustDwon(a, n, i);
}
int end = n - 1;
//建好大堆,将最大值交换置数组的最后,然后排出最后一个元素,对前n-1的数组进行建堆
while(end>0)
{
Swap(&a[0], &a[end]);
AdjustDwon(a, end, 0);
end--;
}
}
对排序的时间复杂度
建堆的时间复杂度:
在堆排序中,首先需要将待排序的序列构建成一个最大堆。构建最大堆的时间复杂度是O(n),其中 n 是待排序序列的长度。这是因为我们只需要对具有父子关系的一半节点进行堆化操作,而这一半节点通常是 n/2。
排序过程的时间复杂度:
堆排序的排序过程包括了 n-1 次交换和堆调整的操作。每次交换涉及到堆顶元素与末尾元素的交换,然后对剩余的 n-1 个元素进行堆调整。堆调整的时间复杂度为O(log n)。因此,排序过程的总时间复杂度为 O((n-1) * log n),约等于O(n log n)。
总体时间复杂度:
将建堆和排序过程的时间复杂度结合起来,堆排序的总体时间复杂度为 O(n + n log n)。
在大 O 表示法中,通常会忽略掉低阶项和常数系数,因此可以简化为 O(n log n)。
堆排序的时间复杂度是相对较好的,且具有原地排序的特点。然而,需要注意的是,堆排序在实际应用中可能会因为其不具备稳定性(相同元素的相对位置可能发生变化)和对缓存的不友好等原因而被其他算法替代。