标签算法

插入法排序

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

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

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

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

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

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

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

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

#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;
    }
}