【8.3】选择排序 (堆排序)

一、直接选择排序

依次选出剩下的未排序记录中的最小记录

直接选择排序性能分析：

• 不稳定
• 空间代价:Θ(1)
• 时间代价
• 比较次数:Θ(n²)
• 交换次数:n-1
• 总时间代价:Θ(n²)

二、堆排序

堆排序:基于最大堆来实现

• 选择类内排序

• 直接选择排序:直接从剩余记录中线性 查找最大记录

• 堆排序:基于最大堆来实现，效率更高

• 选择类外排序

• 置换选择排序

• 赢者树、败方树

最大堆排序过程示意图

堆排序算法:

算法分析:

• 建堆:Θ(n)
• 删除堆顶: Θ(log n )
• 一次建堆，n 次删除堆顶
• 总时间代价为 Θ(nlog n)
• 空间代价为 Θ(1)

思考

• 直接选择排序为什么不稳定?怎么修改一下让它变稳定
• 改写堆排序算法，发现逆序对直接交换

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾