用C语言写一个函数实现这个算法。
/* ai 是要排序的整数数组
* n 是数组中元素的个数
*
* 函数中i，j是计数变量
* min_index是第二部分数组中最小值的元素下标
* min变量暂存第二部分中最小值
* tail是第一部分的尾部位置
* start是第二部分开始扫描的起始位置
*/
static void selection_sort(int *ai, int n)
{
int i, j, k, min_index;
int min;
int tail;
int start;
/* 开始时，第一部分没有元素，尾部在第0个元素 */
tail = 0;
for (i = 0; i < (n-1); i++) {
start = tail;
min = ai[start];
min_index = -1;
for (j = start; j < n; j++) {
if (ai[j] < min) {
min_index = j;
min = ai[j];
}
}
if (min_index != -1) {
/* 找到了最小值，交换元素 */
k = ai[tail];
ai[tail] = ai[min_index];
ai[min_index] = k;
}
tail++;
}
}
这个函数看起来有些复杂，我们来简化一下。从上面看tail其实就是i的位置，start是i的下一个位置，min值是扫描第二部分的第一个元素，把这些简化后，得到下面的函数。
void selection_sort(int *ai, int n)
{
int i, j, k;
int min_index;
for (i = 0; i < (n-1); i++) {
min_index = i;
for (j = i+1; j < n; j++) {
if (ai[j] < ai[min_index])
min_index = j;
}
if (min_index != i) {
/* 交换元素 */
k = ai;
ai = ai[min_index];
ai[min_index] = k;
}
}
}
查抄排序结果
写一个函数来查抄一下排序后的元素顺序有没有错误，方法很简单，在数组中遍历一次，看看前一个元素是否比后一个元素大，假如大就阐明排序堕落了。
void check_result(int *ai, int n)
{
int i;
for (i=0; i<n-1; i++) {
if (ai > ai[i+1]) {
fprintf(stderr, "error, element[%d]=%d, element[%d]=%d\n\n", i, ai, i+1, ai[i+1]);
return;
}
}
fprintf(stdout, "element is sorted.\n\n");
}
写一个程序测试一下排序结果。
int main(int argc, char *argv[])
{
static int chaos[16] = {23, 6, 235, 89, 4, 12, 76, 35, 129, 30, 77, 15, 61, 44, 49, 88};
int array[16];
fprintf(stdout, "test for bubble_sort function.\n\n");
memcpy(array, chaos, 16*sizeof(int));
bubble_sort(array, 16);
check_result(array, 16);
fprintf(stdout, "test for selection_sort function.\n\n");