8.3.1 冒泡排序

教材导航 · 第8章

原书定位

印刷页P347起,对应PDF第359页。下文为目视整理的知识提要;完整内容见原书对照。

逐对比较相邻记录,逆序则交换,一趟把一个极值推到最终位置。扫描方向决定最小值到前端还是最大值到后端;确定的前缀或后缀不再参与。

只交换严格逆序的记录,故稳定。带“本趟无交换即结束”标记时最好 O(n)O(n),平均与最坏 O(n2)O(n^2),辅助空间 O(1)O(1)。相邻交换次数等于初始逆序对数,每次交换若按三次赋值统计,移动数再乘 3。

冒泡排序过程

冒泡排序过程,原书P347。

对应练习

8.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P347,PDF第359页

原书对照,原书P348,PDF第360页