选择排序
1.原理
它是找出最大数(或最小数)放到最前面,它不再是数组前后比较,而是在一轮里一直拿一个位置数跟后面的比较。
通俗的说就是在排队的时候,先拿一号依次跟后面的每一个人都比较,如果和它比较的人比一号小,则他俩换位,小的这个人站第一排,拿这个人跟后面比,以此类推,确保第一个是最低的。第二轮从第二个人开始,重复上面的操作,不在动排好的人
假设10个人排队int a[10];
比较第一轮:
for(int i=0;i<9;i++){
for(int j=i+1;j<10;j++){
if(a[i]>a[j]){
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
需要注意的是for循环里的三个表达式,我们已经把第一个赋给max,所以就直接从第二个开始,也就是从索引1开始,i小于10
2.举例
1.题目
输入10个数对其进行排序
2.代码
#include "stdio.h"
int main() {
int t, a[10];
for (int i = 0; i < 10; i++) {
scanf("%d", &a[i]);
}
for (int i = 0; i < 9; i++) {
for (int j = i + 1; j < 10; j++) {
if (a[i] > a[j]) {
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}
for (int i = 0; i < 10; i++) {
printf("%d\t", a[i]);
}
return 0;
}
选择排序的交换操作介于 0 和 (n - 1)次之间。选择排序的比较操作为 n (n - 1) / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1) 次之间。比较次数O(n^2),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。交换次数O(n),最好情况是,已经有序,交换0次;最坏情况交换n-1次,逆序交换n/2次。交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。