插入法排序
何谓算法？算法就是计算机解决问题的方法和步骤。之所以强调计算机三个字，是因为计算机处理问题的方式和我们人类解决问题的方式有所不同。比如，在电视剧《宫》里看到一个智力题：把一头大象放进骄子里需要哪几个步骤？答案是：第一步，掀开轿帘；第二步，把大象放进去；第三步，放下轿帘。当然，可行性我们暂时不去考虑。然而，对于计算机来说，它没法去掀开轿帘，或者把大象放进轿子里。它只能通过计算机系统特有的指令去处理数据，以此来解决问题。
知道了什么是算法，那么如何去描述问题和算法呢？
以排序问题为例，描述一个问题可以用以下的方式：
输入：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;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
