何谓算法?算法就是计算机解决问题的方法和步骤。之所以强调计算机三个字,是因为计算机处理问题的方式和我们人类解决问题的方式有所不同。比如,在电视剧《宫》里看到一个智力题:把一头大象放进骄子里需要哪几个步骤?答案是:第一步,掀开轿帘;第二步,把大象放进去;第三步,放下轿帘。当然,可行性我们暂时不去考虑。然而,对于计算机来说,它没法去掀开轿帘,或者把大象放进轿子里。它只能通过计算机系统特有的指令去处理数据,以此来解决问题。

知道了什么是算法,那么如何去描述问题和算法呢?

以排序问题为例,描述一个问题可以用以下的方式:

输入:n个整数,存放于一个数组a之中。

输出:这n个数在数组a之中按从小到大的顺序存放。

给出了一个问题的输入和要求的输出,这个问题就确定了。描述一种算法,可以用伪代码或者是计算机语言。

对于排序问题,有多种算法。下面谈谈Insertion sort——插入法排序:

插入法排序的大概思想和摸扑克牌类似:当然,我们要求只有一个人摸牌,初始的数组就是放在桌上的一堆牌,而拿到手上的牌是排好序的。当我们摸起一张牌时,会按大小插入到已排好序的手牌之中。下面是基于linux系统,用C语言对改算法的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#define MAX 10

int sort(int*);

int main()
{
int input_array[MAX];
int ret,i;

printf("Please input the numbers :\n");
for(i = 0; i < MAX; i++){
scanf("%d", &input_array[i]);
}

printf("The numbers before being sorted :\n");
for(i = 0; i < MAX; i++){
printf("%d ", input_array[i]);
}
printf("\n");

ret = sort(input_array);
printf("The sorted numbers :\n");
for(i = 0; i < MAX; i++){
printf("%d ", input_array[i]);
}
printf("\n");

return 0;
}

int sort(int* p)
{
int i,j,temp;
for(i = 1; i < MAX; i++){
temp = p[i];
for(j = i-1; j >= 0 && p[j] > temp; j--){
p[j+1] = p[j];
}
p[j+1] = temp;
}
}