选择排序

[Jerry]

教学目标：通过解决一个简单的问题，来描述编程解决问题的一般步骤。

问题：设计一个程序，把n个整数排序，其中n>=1。

（面对问题，首先确定解决问题的基本思路。）
基本思路：从未被排序的整数中找出最小的整数，将其放在已排序整数列表中的下一个位置。

（选定数据结构，这些整数初始时应该放在哪里，以及如何存放，结果应该存放在那里。）
将这些数存放在一个数组list中，其中第i个整数存放在数组的第i个位置list[i]中（0
<= i < n）。

（写出粗框的（带自然语言描述的）的算法，原则是尽量不含有任何子步骤。）
算法的粗框代码：

for (i =0; i < n; i++){

检查list[i]到list[n-1]并假定最小的整数存储在list[min]中
;

交换list[i]与list[min]的值;
}

（对比较明确的步骤进行分析，并形成程序。）
第一个子任务代码：

void swap( int *x, int *y)
/* 两个参数都是指针变量，指向两个整型数 */
{
int temp = *x;
*x = *y;
*y = temp;
}

（对比较含糊的步骤进行分析和求精。）
函数sort(list,
n)将把n(n>=1)个正整数排序。排序后的结果存放在list[0],
..., list[n-1]中，且满足list[0] <= list[1] <= ... <= list[n-1]。

程序的代码：
#include <stdio.h>
#include <math.h>
#define MAX_SIZE 101
#define SWAP(x,y,t) ((t) = (x), (x) = (y), (y) = (t))

void sort( int [], int );
void main( void )
{
int i, n;
int list[MAX_SIZE];
printf("Enter the number of numbers to generate: ");
scanf("%d", &n);
if( n<1 || n>MAX_SIZE ){
fprintf(stderr, "Improper value of n\n");
exit(1);
}
for (i = 0; i < n; i++) {
list[i] = rand() % 1000;
printf("%d ", list[i]);
}
sort(list, n);
printf("\n Sorted array:\n");
for (i = 0; i < n; i++)
printf("%d ", list[i]);
printf("\n");
}
void sort(int list[], int n)
{
int i, j, min, temp;
for (i = 0; i < n-1; i++){
min = i;
for (j = i+1; j < n; j++)
if (list[j] < list[min])
min = j;
SWAP(list[i], list[min], temp);
}
}

算法分析：
1、确定实例特征 该算法的实例特征为"比较"
2、估计最好的和最坏的情况
3、给出结论