8.3.1 冒泡排序
原书定位
印刷页P347起,对应PDF第359页。下文为目视整理的知识提要;完整内容见原书对照。
逐对比较相邻记录,逆序则交换,一趟把一个极值推到最终位置。扫描方向决定最小值到前端还是最大值到后端;确定的前缀或后缀不再参与。
只交换严格逆序的记录,故稳定。带“本趟无交换即结束”标记时最好 ,平均与最坏 ,辅助空间 。相邻交换次数等于初始逆序对数,每次交换若按三次赋值统计,移动数再乘 3。

冒泡排序过程,原书P347。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P347起,对应PDF第359页。下文为目视整理的知识提要;完整内容见原书对照。
逐对比较相邻记录,逆序则交换,一趟把一个极值推到最终位置。扫描方向决定最小值到前端还是最大值到后端;确定的前缀或后缀不再参与。
只交换严格逆序的记录,故稳定。带“本趟无交换即结束”标记时最好 ,平均与最坏 ,辅助空间 。相邻交换次数等于初始逆序对数,每次交换若按三次赋值统计,移动数再乘 3。

冒泡排序过程,原书P347。

