|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 > 简单排序 >
|
|
考试要求：掌握
相关知识点：3个
|
|
|
|
|
n个记录进行简单选择排序的基本方法是：通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1≤i≤n）个记录进行交换，当i等于n时所有记录有序排列。
|
|
|
|
|
|
|
简单选择排序法在最好情况下（待排序列已按关键码有序）不需要移动元素，因此n个元素排序时的总移动次数为0次。在最坏情况下（元素已经逆序排列），每趟排序移动记录的次数都为3次（两个数组元素交换值），共进行n-1趟排序，总移动次数为3（n-1）。无论在哪种情况下，元素的总比较次数为 。
|
|
|
|
由此，简单选择排序是一种不稳定的排序方法，其时间复杂度为O（n2）。排序过程中仅需要一个元素的辅助空间用于数组元素值的交换，空间复杂度为O（1）。
|
|
|
