小朋友学C语言（27）：选择排序
（一）基本原理（由小到大）：
如果有n个数，需要比较n-1轮： 第1轮，将n个数中最小的数与a[0]对换，当然若a[0]就是最小的数则不用对换。 第2轮，将a[1]到a[n-1]中最小的数与a[1]对换，当然若a[1]就是最小的数则不用对换。 …… 第n-1轮，将最后的两个数，即a[n-2]与a[n-1]比较，若a[n-2] > a[n-1]，则对换。至此，排序完毕。
（二）例子
例1：a[] = {5, 1, 2, 3, 4}
分析 ：需要比较n - 1 = 4轮。
第1轮，a[1]=1是5个元素中最小的，并且a[1]不等于a[0]，则对换a[1]与a[0]。对换后数组变为a[] = {1,5,2,3,4}
第2轮，对于a[]的后四个元素来说，a[2]=2是最小的，并且a[2]不等于a[1]，则对换a[2]与a[1]。对换后数组变为a[] = {1, 2, 5, 3, 4}
第3轮，对于a[]的后三个元素来说，a[3]=3是最小的，并且a[3]不等于a[2]，则对换a[3]与a[2]。对换后数组变为a[] = {1, 2, 3, 5, 4}
第4轮，对于a[]的最后两个元素来说，a[4]=4是最小的，并且a[4]不等于a[3]，则对换a[4]与a[3]。对换后数组变为a[] = {1, 2, 3, 4, 5} 至此，排序结束。
例2：b[] = {1, 3, 5, 4, 2, 6}
分析：需要比较n - 1 = 5轮。
第1轮，b[0]就是六个元素中最小的数，不用对换。
第2轮，对于后五个元素来说，b[4] = 2是最小的数，b[4]不等于b[1]，则对换b[4]和b[1]，对换后，数组变为b = {1, 2, 5, 4, 3, 6}。
第3轮，对于后四个元素来说，b[4] = 3是最小的数，b[4]不等于b[2]，则对换b[4]和b[2]，对换后，数组变为b = {1, 2, 3, 4, 5, 6}。
第4轮，对于后三个元素来说，b[3] = 4是最小的数，不用对换。
第5轮，对于最后两个元素来说，b[4] = 5是最小的数，不用对换。至此排序结束。
（三）编程实现
#include<stdio.h>
// 打印数组，方便观察结果
void print_array(int a[], int n)
{
for(int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
// 选择排序算法
void select_sort(int a[],int n)
{
int i, j, min;
// i代表比较的轮数，i的取值范围是0到n-2，共n-1轮
for(i = 0; i < n - 1; i++)
{
/* min表示本轮比较中，最小元素的下标。
这里先赋值为i，也就是本轮比较的首个元素所在的位置。
下面根据比较结果，有可能变化，也有可能不变。*/
min = i;
// a[i]右侧的所有元素都与a[i]比较
for(j = i + 1; j < n; j++)
{
// 若发现有更小的数，把该数的下标赋值给min
// min在这个循环里可能会不断变化，最后会停在最小数所在的下标
if(a[j] < a[min])
{
min = j;
}
}
// 如果min与i不相等，说明a[i]右侧有比a[i]更小的数（可能不止一个）
// 则a[min]就是a[i]右侧最小的数，将a[i]与a[min]互换位置
if(min != i)
{
a[min] ^= a[i];
a[i] ^= a[min];
a[min] ^= a[i];
}
printf("After %d round sort, the array is:", i + 1);
print_array(a, n);
}
}
int main()
{
int b[] = {5, 1, 2, 3, 4};
int cnt = sizeof(b) / sizeof(int);
select_sort(b, cnt);
return 0;
}运行结果：
After 1 round sort, the array is:1 5 2 3 4
After 2 round sort, the array is:1 2 5 3 4
After 3 round sort, the array is:1 2 3 5 4
After 4 round sort, the array is:1 2 3 4 5 （四）程序分析：
n - 1 = 4轮比较中，共产生了十次循环。分别是 i = 0, j = 1 i = 0, j = 2 i = 0, j = 3 i = 0, j = 4 i = 1, j = 2 i = 1, j = 3 i = 1, j = 4 i = 2, j = 3 i = 2, j = 4 i = 3, j = 4
具体执行如下：
i = 0, min = 0 j = 1, 第一个if成立，min = 1 j = 2, 第一个if不成立，min仍然为1 j = 3, 第一个if不成立，min仍然为1。 j = 4, 第一个if不成立，min仍然为1。内循环结束，跳出内循环 。第二个if成立，a[0]与a[min]（即a[1]）对换，数组变为{1, 5, 2, 3, 4}
i = 1, min = 1 j = 2, 第一个if成立，min = 2 j = 3, 第一个if不成立，min仍然为2。 j = 4, 第一个if不成立，min仍然为2。内循环结束，跳出内循环 。第二个if成立，a[1]与a[min]（即a[2]）对换，数组变为{1, 2, 5, 3, 4}
i = 2, min = 2 j = 3, 第一个if成立，min = 3 j = 4, 第一个if不成立，min仍然为3。内循环结束，跳出内循环 。第二个if成立，a[2]与a[min]（即a[3]）对换，数组变为{1, 2, 3, 5, 4}
i = 3, min = 3 j = 4, 第一个if成立，min = 4。内循环结束，跳出内循环 。第二个if成立，a[3]与a[min]（即a[4]）对换，数组变为{1, 2, 3, 4, 5} 至此，外循环结束，跳出外循环，继续执行下面的代码。
（五）作业
编写代码； 断点调试； 默写。