选择排序详解
选择排序的核心思想在于每一趟从待排序列中选取一个关键字值最小的记录,将其放到已排序序列的末尾。第 1 趟从 n 个记录中选出最小值,第 2 趟从剩余的 n-1 个记录中选出次小值,依此类推,直到所有记录归位。
直接选择排序
核心思路
首先在所有记录中找出关键字最小的记录,与第一个记录交换;然后在剩余记录中找次小记录,与第二个记录交换。重复此过程,直到整个序列有序。

执行示例
假设待排序序列为 { 5, 3, 6, 4, 7, 1, 8, 2 }。初始视为无序序列,每趟遍历后,有序区长度 +1,无序区长度 -1。图示中红色标记代表已排序区域,实际推导时可用方框标注。
代码实现
public void selectSort() {
RecordNode temp;
// 进行 i-1 次遍历,this.curlen 为数组长度
for(int i=0; i<this.curlen-1; i++) {
int min = i;
// 在无序区寻找最小值索引
for(int j=i+1; j<this.curlen; j++) {
if (r[j].key.compareTo(r[min].key) < 0) {
min = j;
}
}
// 如果找到更小的元素,则交换位置
if (min != i) {
temp = r[i];
r[i] = r[min];
r[min] = temp;
}
}
}
性能分析
直接选择排序的时间复杂度始终为 O(n²),空间复杂度为 O(1)。虽然移动次数较少,但比较次数固定,稳定性较差(不稳定排序)。
树形选择排序
核心思路
先对 n 个记录两两比较,将较小者作为优胜者上升到父结点。重复此过程,直到选出最小关键字值。整个过程可用一棵含有 n 个叶子结点的完全二叉树表示。







