一、算法思想
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据有序。
选择排序的基本思想是:每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。选择排序有简单选择排序、堆排序等多种算法。下面的分析、操作、程序均以简单选择排序算法为例进行讲解。
二、操作过程
初始状态： (49) 38 65 97 76 13 27 49 32 13
第1趟： i k
13 (38) 65 97 76 49 27 49 32 13
第2趟： i k
13 13 (65) 97 76 49 27 49 32 38
第3趟： i k
13 13 27 (97) 76 49 65 49 32 38
第4趟： i k
13 13 27 32 (76) 49 65 49 97 38
第5趟： i k
13 13 27 32 38 (49) 65 49 97 76
第6趟： i,k
13 13 27 32 38 49 (65) 49 97 76
第7趟： i k
13 13 27 32 38 49 49 (65) 97 76
第8趟： i,k
13 13 27 32 38 49 49 65 (97) 76
第9趟： i k
13 13 27 32 38 49 49 65 76 97
三、参考程序
#include <stdio.h>
#define MAX 10
/* 从键盘输入n个数，保存在数组中 */
void input(int arr[], int n);
/* 使用简单选择排序对数组中的元素按非递减有序排列 */
void sort(int arr[], int n);
/* 输出数组中的所有元素 */
void display(int arr[], int n);
int main()
{
int arr[MAX];
printf("请输入%d个数：\n", MAX);
input(arr, MAX);
printf("排序前：\n");
display(arr, MAX);
sort(arr, MAX);
printf("排序后：\n");
display(arr, MAX);
return 0;
}
/* 从键盘输入n个数，保存在数组中 */
void input(int arr[], int n)
{
int i;
for(i=0; i<n; i++)
{
scanf("%d", &arr[i]);
}
}
/* 使用简单选择排序对数组中的元素按非递减有序排列 */
void sort(int arr[], int n)
{
int i, j, k;
int temp;
for(i=0; i<n-1; i++)
{
k = i;
for(j=i+1; j<n; j++)
{
if(arr[j] < arr[k])
{
k = j;
}
}
if(k != i)
{
temp = arr[k];
arr[k] =arr[i];
arr[i] = temp;
}
}
}
/* 输出数组中的所有元素 */
void display(int arr[], int n)
{
int i;
for(i=0; i<n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
四、运行测试
请输入10个数：
49 38 65 97 76 13 27 49 32 13
排序前：
49 38 65 97 76 13 27 49 32 13
排序后：
13 13 27 32 38 49 49 65 76 97