警告该文章涉嫌严重的标题党，博主胆小怕事欢迎狂喷
个人喜欢将堆排序设计为三个层次分三个函数层层递进实现
1.将一个局部的堆（二叉堆）实现大根堆
解释一些概念
(1)二叉堆：将元素（这里不严谨的指代所有实数）按照二叉树的结构以数组下标映射的方式存储。
对于每个元素，我们关心其与子节点间的大小关系(如果存在)
对于数组下标为i的元素(从0开始)
其左子节点的下标(若存在)
lt = 2 * i + 1;
其右子节点的下标为(若存在)
rt = 2 * i + 2;
(2)大根堆
对于每个结点，其相对于左右子节点的值，为最大(隐含着根节点为局部大根堆最大值)
习惯上我们会建成一个完全二叉树形式的大根堆
补充完废话，直接上代码解析一哈
void maxHeapify(vector<int> & nums, int i, int heapSize)
{
//heapSize = nums.size();
int lt = 2 * i + 1, rt = 2 * i + 2, largest = i;
//lt,rt说过了不谈，largest我们用来动态存储三个结点之间的最大值(当前结点i与其左右子节点)
if (lt < heapSize && nums[lt] > nums[largest]) {
largest = lt;}
if (rt < heapSize && nums[rt] > nums[largest]) {
largest = rt;}
if (largest != i) //如果最大值不为当前结点
{
swap(nums[i], nums[largest]); //交换两个结点的位置
maxHeapify(nums, largest, heapSize);//小值下滤
}
}
2.实现建立全局的大根堆
从第一个非叶结点开始，向上遍历将最大值放到根的位置
void buildMaxHeap(vector<int> & nums, int heapSize)
{
for (int i = heapSize / 2; i >= 0; --i)
{
maxHeapify(nums, i, heapSize);
}
//对于每次遍历，我们利用1中实现的子过程，实现了以当前结点为根的局部大根堆的构建。在下一次遍历中，其会作为子节点与新的上面的根作比较
}
3.初始化大根堆及每次遍历将元素"插入"对应位置
这里所说的插入实际上是对于第i次遍历，我们把当前全局大根堆根值与第i大元素应该存在的位置上的元素做交换
void HeapSort(vector<int> & nums)
{
int heapSize = nums.size();
buildMaxHeap(nums, heapSize);
for (int i = nums.size() - 1; i >= 0; --i) //从大到小排序
{
//第i次遍历构建局部大根堆然后将局部大根堆最大值与末端位置元素做交换并放到第i大的元素的位置
swap(nums[0], nums[i]);
heapSize -= 1;
maxHeapify(nums, 0, heapSize);
}
}
总体代码
void maxHeapify(vector<int> & nums, int i, int heapSize)
{
int lt = 2 * i + 1, rt = 2 * i + 2, largest = i;
if (lt < heapSize && nums[lt] > nums[largest]) {
largest = lt;}
if (rt < heapSize && nums[rt] > nums[largest]) {
largest = rt;}
if (largest != i)
{
swap(nums[i], nums[largest]);
maxHeapify(nums, largest, heapSize);
}
}
void buildMaxHeap(vector<int> & nums, int heapSize)
{
for (int i = heapSize / 2; i >= 0; --i)
{
maxHeapify(nums, i, heapSize);
}
}
void HeapSort(vector<int> & nums)
{
int heapSize = nums.size();
buildMaxHeap(nums, heapSize);
for (int i = nums.size() - 1; i >= 0; --i) //从大到小排序
{
//第i次遍历构建局部大根堆然后将局部大根堆最大值与末端位置元素做交换并放到第i大的元素的位置
swap(nums[0], nums[i]);
heapSize -= 1;
maxHeapify(nums, 0, heapSize);
}
}
int main(void)
{
HeapSort(nums);
//略
}
读者阅读实现后，可以尝试完成leetcode板子题ac进行练习
977.有序数组的平方
睡了睡了
