目录
题目
本题要求实现一个用选择法对整数数组进行简单排序的函数。
函数接口定义：
void sort( int a[], int n );
其中a是待排序的数组，n是数组a中元素的个数。该函数用选择法将数组a中的元素按升序排列，结果仍然在数组a中。
裁判测试程序样例：
#include <stdio.h>
#define MAXN 10
void sort( int a[], int n );
int main()
{
int i, n;
int a[MAXN];
scanf("%d", &n);
for( i=0; i<n; i++ )
scanf("%d", &a[i]);
sort(a, n);
printf("After sorted the array is:");
for( i = 0; i < n; i++ )
printf(" %d", a[i]);
printf("\n");
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例：
4
5 1 7 6
输出样例：
After sorted the array is: 1 5 6 7
代码
void sort( int a[], int n )
{
int k;//最小值下标
for(int i=0;i<n-1;i++)//第一个未排序元素的下标
{
k=i;
for(int j=i+1;j<n;j++)//在未排序元素中遍历找出最小值
{
if(a[k]>a[j])
{
k=j;
}
}
//已找到未排序元素中的最小值a[k]
//和第一个未排序的元素交换位置
if(k!=i)
{
int min=a[k];
a[k]=a[i];
a[i]=min;
}
}
}
测评详情
思路
选择法排序就是找出未排序的元素中最小的一位，将min和第一个未排序的元素交换位置，形成两部分：1.从小到大排序的已排序部分；2.未排序部分。直到未排序部分没有元素，则全部排序完成。
使用选择排序的方法将数列1，5，6，7。按照从小到大的顺序排序:
首先，在数列中找到最小的元素1，将其放在第一位。
接着，在剩余的数列中再次找到最小的元素5，将其放在第二位。
然后，继续在剩余的数列中找到最小的元素6，将其放在第三位。
最后，在剩余的数列中找到最小的元素7，将其放在第四位。
这样，数列5，1，7，6就被排成了从小到大的顺序，为1，5，6，7。
- 思路流程
-
重复（元素个数-1）次 { 把**第一个没有排序过**的元素设置为最小值 遍历比较每个**没有排序过**的元素，找出真正的最小值与第一个没有排序过的元素交换 }
图
第一轮循环遍历未排序的元素
把现在的最小值设置成第一个元素，即min=a[0],然后遍历剩下没有排序过的元素，找到真正的最小值。
遍历到a[1]
a[1]<min,则将a[1]设为新的最小值，min=a[1]。
遍历到a[2]，min<a[2]
遍历到a[3]，min<a[3]
第一轮遍历完，找到此轮未排序元素的最小值min，将min值与第一个未排序的元素a[0]交换
此时，a[0]即为排序过了的元素
以此类推，得到从小到大的一列1 5 6 7
问题
定义min来保存每轮排序的最小值，但是得到最小值之后该怎么将是最小值的那个元素与第一个未排序的元素交换呢？再定义一个k来存储最小值的下标吗？
答：可以这么做，如：
int min,k;//min为最小值，k为最小值下标
for (int i = 0; i < n - 1; i++)//第一个未排序元素的下标
{
min = a[i];
k = i;
for (int j = i + 1; j < n; j++)//在未排序元素中遍历找出最小元素
{
if (min > a[j])
{
min = a[j];
k = j;
}
}
//找出最小值，将最小值与第一个未排序元素交换
if (k != i)
{
a[k] = a[i];
a[i] = min;
}
}
但是也可以只设置k为最小值下标，用a[k]表示最小值，但最后交换元素时要定义一个新变量来帮助交换元素，如：
int k;//k为最小值下标
for (int i = 0; i < n - 1; i++)//第一个未排序元素的下标
{
k = i;
for (int j = i + 1; j < n; j++)//在未排序元素中遍历找出最小元素
{
if (a[k] > a[j])
{
k = j;
}
}
//找出最小值，将最小值与第一个未排序元素交换
if (k!=i)
{
int min = a[k];
a[k] = a[i];
a[i] = min;
}
}
总而言之，选择排序法就是在未排序数中找到最小值并与第一个未排序数交换，最小值用min或a[k]表示都可以，重点是要知道最小值的下标k，才能和第一个元素a[i]交换。