选择排序:(从小到大)的基本思想是, 首先, 选出最小的数, 放在第一个位置; 然后, 选出第二小的数, 放在第二位置; 以此类推, 直到所有的数从小到大排序.
代码飞起来~
#include <stdio.h>
void select_sort(int arr[], int len) { //每次从后边选择一个最小值
for(int i= 0; i< len-1; i++) { //只选择n-1轮
int min = i; //找出第i小的数所在的位置
for (int j = i+1; j < len; j++) {
if(arr[min] > arr[j]) {
min = j;
}
}
if(min != i) { //将第i小的数, 放在第i个位置; 如果刚好,就不用交换
int temp = arr[i];
arr[i] = arr[min];
arr[min] =temp;
}
}
}
int main() {
int arr[] = {112, 4, 2, 5, 33, 6, 8, 9, 7, 16};
select_sort(arr, 10);
for(int i = 0; i < 10; i++)
printf("%d ", arr[i]);
}
运行结果:
==注意:==选择排序是一种不稳定的. 每次都能确定一个元素所在的最终位置, 比较次数和初始序列有关.
时间复杂度为O(N^2), 空间复杂度为O(1).
