大堆: 根节点值大于子节点的值,对应为升序序列。
小堆: 根节点值小于子节点的值,对应为降序序列。
堆排序实现的两个步骤:
- 创建堆
- 堆排序
下述例子是进行大堆创建:
- 创建大堆:图例
创建步骤:
- 寻找最后一个分支的根节点(记为pos)
- pos挨个减小,对每个分支,都进行大堆排列。根节点比子节点值大
- 终止条件:pos < 0,不再进行大堆创建。
- 大堆排序:升序
排序步骤:
- 堆顶元素和末尾元素值交换
- 最大值排在末尾,该值不再做交换
- 调整堆结构,满足大堆定义。重复执行步骤1,2,直到达到堆顶位置
C代码实现:
void ShiftDown(int *arr, int left, int right, int pos)
{
int i = pos;//根节点
int j = 2 * i + 1 + left;//子节点
int n = right - left;
int tmp = arr[i];
while (j < n)
{
if (j + 1 < n && arr[j + 1] > arr[j])//找子节点最大值
j++;
if (arr[j] > tmp)//子节点比根节点大
{
arr[i] = arr[j];//根节点值等于子节点的值
i = j;//往下调整
j = 2 * i + 1;
}
else
break;
}
arr[i] = tmp;//循环退出,根节点的值等于最开始的arr[pos]值
}
void HeapSort(int *arr, int left, int right)
{
int n = right - left;
int pos = (n - 2) / 2 + left;//寻找最后一个分支的根节点
while (pos >= 0)//建堆
{
ShiftDown(arr, left, right, pos--);
}
int end = n;
while (end >= 2)//排序
{
end--;
Swap(&arr[end], &arr[left]);//交换堆顶和尾部元素
ShiftDown(arr, left, end, left);
}
}
堆排序整体步骤:
- 建堆:大堆或小堆。先找到最后一个分支的根节点。再对个分支都进行调整。
- 排序:堆顶和末尾数据交换,调整堆结构,尾部下标-1。再进行排序。
特性总结:
- 时间复杂度:O(N*logN)
- 空间复杂度:O(1)
- 稳定性:不稳定