8.4.1 简单选择排序

教材导航 · 第8章

原书定位

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

每趟记录剩余部分最小值的位置,扫描结束后与当前首位置交换。每趟确定一个最小元素,前缀已在全局最终位置。

比较总数始终 n(n−1)/2n(n-1)/2,时间 O(n2)O(n^2),空间 O(1)O(1)。最多 n−1n-1 次交换,移动较少;跨位置交换可能改变相等记录顺序,因此不稳定。可用于数组或链表,但实现方式不同。

对应练习

8.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P358,PDF第370页