思路
- 确定第1位：从0～length-1中找出最小的数，与第1位的元素交换位置。
- 确定第2位：从1～length-1中找出最小的数，与第2位的元素交换位置。
- ……
- 确定第n-1位：……
从？～？中找出最小的数的思路是：声明int min记录最小值；遍历数组，当元素比min小时，把元素赋值给min；遍历结束时，min即为最小值。
平均时间复杂度：O(n2)
实现
void select_sort(const int* a, int length){
for(int i = 0; i < length-1; i++){
int minIndex = i;
for(int j = i+1; j < length; j++){
if(a[j] < a[minIndex]){
minIndex = j;
}
}
if(minIndex != i){
swap(a[i], a[minIndex]);
}
}
}
关键点注释
- 1层遍历。
- 遍历从0到length - 1，即：“思路”中确定第1位～确定n - 1位。
- 遍历体分为两部分。
- 第1部分找出子数组中最小值。
- 第2部分把最小值与目标索引的值交换。
