堆排序

堆排序

2025/6/6 14:50:52 来源：https://blog.csdn.net/shylyly_/article/details/142219280 浏览: 次关键词：堆排序

一：思想

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。

动图：

二：实现思路

假设：现在对一个7个整形的数组进行升序堆排（2 1 5 7 4 3 6）结果应该为（1 2 3 4 5 6 7）

第一步：对接受到的数组（2 1 5 7 4 3 6）进行建堆大堆（采取向下调整建堆）

第二步：对得到的大堆，每次交换第一个和最后一个元素，然后输出最后一个元素（最大值），此时最后一个元素不再当作堆里的元素了，最后再把剩下元素重新调整为最大堆，最后输出的就是一个升序的数组！

如上图所示：建立大堆一次，就交换头尾然后end--一次，然后再向下调整建立大堆.....就这样不断进行，最终数组就是1 2 3 4 5 6 7了

总结：

大堆会让最大的在最上面，所以我们把根与最后的元素交换，然后end--，对剩余的继续建大堆...

运用大堆的性质，逐渐的把每次堆里最大的放在数组的最后。

三：代码

//向下调整函数 建立大堆
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1; // 初始化child为parent的左孩子while (child < n) // 当child未越界时循环{if (child + 1 < n && a[child] < a[child + 1]) // 如果右孩子存在且左孩子大于右孩子{child++; // 将child指向右孩子}if (a[child] > a[parent]) // 如果孩子节点大于父节点，则违反了大堆的性质{Swap(&a[child], &a[parent]); // 交换孩子节点和父节点的值parent = child; // 更新parent为交换后的位置child = parent * 2 + 1; // 更新child为新的parent的左孩子}else{break; // 如果父节点已经不小于任何一个孩子节点，则调整完毕，退出循环}}
}
//堆排
void HeapSort(int* a, int n)
{for (int i = (n - 2) / 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--; // 减少堆的大小}
}