《算法导论》第六章-堆排序（伪代码）

蔚落 2022-08-13 07:00 379阅读 0赞

堆排序

根据《算法导论》中的伪代码，改写如下，可能更好理解

伪代码：

//建堆,运行时间的界T(n) =O(N)

BuildHeap(A)

n = length(A)

for i = n/2 downto 1 do //从非叶子节点开始，自底往上，使A变成最大堆

Max\_Heapify(A, i, n)

end

//调整为最大堆 ,T(n) = O(lgn)

Max\_Heapify(A,idx,max) //idx：数组开始的下标，max：最大的数组下标  
left = 2\*idx  
right = 2\*idx  
if(left<max and A\[left\]>A\[idx\]) then  
largest = left  
else  
largest = idx  
if(right < max and A\[right\]>A\[largest\]) then  
largest = ritht  
  
if(largest != idx) then  
exchange A\[largest\] with A\[idx\]  
Max\_Heapify(A,largest,max) //交换位置后，还需要调整它的子树  
end

HeapSort(A)

BuildHeap(A)

for i = length(A) downto 2 do

exchange A\[1\] with A\[i\] //把最大堆根节点与最后一个互换

Max\_Heapify(A,1, i-1) //把交互后的排除在堆之外，重新从1到i-1,调整堆

end

性能分析:  
  
  
时间复杂度:  
  
  
堆是一个完全二叉树,设树高为k=log2n+1,从根到叶的调整,关键码比较的次数为2(k-1)，交换的次数至多为k次。所以比较的次数不超过  
  
  
2\*(log2(n-1)+log2(n-2)+....+log22)<2nlog2n  
  
  
而比较的次数不超过4n.所以堆排序的时间复杂度为O(nlogn).  
  
  
空间复杂度:  
  
  
需要一个单元的辅助空间用于交换,所以辅助空间为O(1).  
  
  
稳定性:  
  
  
堆排序调整过程中存在着交换,所以堆排序是一个不稳定的排序算法。

发表评论取消回复

表情：

评论列表（有 0 条评论，379人围观）

还没有评论，来说两句吧...

相关阅读

相关算法导论学习笔记第七章快速排序

快排最坏时间复杂度为θ（n²），但它的平均性能很好，通常是实际排序应用中最好的选择，它的期望时间复杂度为θ（nlgn），且θ（nlgn）中隐含的常数因子非常小，且它还能进行原址

青旅半醒/ 2023年01月14日 01:45/ 0 赞/ 153 阅读

相关算法导论学习笔记第六章堆排序

实际中，待排序的数很少是单独的数值，它们通常是称为记录的数据集的一部分，每个记录包含一个关键字，即排序问题中要重排的值，记录的剩余部分由卫星数据组成，通常是要与关键字一同存取的

约定不等于承诺〃/ 2022年11月18日 08:05/ 0 赞/ 203 阅读

相关堆排序----(排序算法六)

1.算法原理 2.算法实现 include <stdio.h> //printArray打印出数组 void

桃扇骨/ 2022年09月17日 14:16/ 0 赞/ 145 阅读

相关《算法导论》第七章-快速排序（伪代码）

快速排序伪代码： QuickSort(A,p,r) if p<r q = Partition(A,p,r) //确定划分位置 QuickSort(A,p,q

旧城等待，/ 2022年08月13日 08:28/ 0 赞/ 295 阅读

相关《算法导论》第六章-优先级队列（伪代码）

优先级队列伪代码： //返回优先级队列的最大值 Heap\_Max(A) return A\[1\] end 运行时间为Θ(1) //去

蔚落/ 2022年08月13日 07:58/ 0 赞/ 156 阅读

相关《算法导论》第六章-堆排序（伪代码）

堆排序根据《算法导论》中的伪代码，改写如下，可能更好理解伪代码： //建堆,运行时间的界T(n) =O(N) BuildHeap(A) n = len

蔚落/ 2022年08月13日 07:00/ 0 赞/ 380 阅读

相关一头扎进算法导论-堆排序

定义：堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全

深碍√TFBOYSˉ_/ 2022年07月15日 18:46/ 0 赞/ 193 阅读

相关算法导论第6章堆排序答案

一、概念 1.堆的定义与性质（1）堆是一种数组对象（2）堆可以被视频一棵完全二叉树，二叉树的层次遍历结果与数组元素的顺序对应，树根为A\[1\]。对于数组中第

╰+哭是因爲堅強的太久メ/ 2022年05月15日 11:40/ 0 赞/ 220 阅读

相关算法导论第8章线性时间排序答案

一、概念 1.比较排序比较排序是指通过输入元素间的比较来确定各元素次序的排序算法。任何比较排序在最坏情况下都要用O(nlgn)次比较来进行排序合并排序和堆

怼烎@/ 2022年05月14日 03:26/ 0 赞/ 235 阅读

相关算法导论第7章快速排序答案

一、概念快速排序是基于分治模式的，选择一个数作为主元，经过一遍扫描，所有小于主元的数放在主元的左边，大于主元的数放在主元的右边，这样就划分成了两组数据。然后对两组数分别

﹏ヽ暗。殇╰゛Y/ 2022年05月14日 00:45/ 0 赞/ 275 阅读