程序的灵魂是“算法”，那么什么是算法？我们所写的程序都是有具体的任务要执行的，但是可以有多种方法来达到同一种目的，而我们需要做的就是选择其中最好的那一种方法，并用C语言将它表达出来。其实这段时间我一直在强调，编程难的不是写程序，而是如何设计好工作方法也就是这里的算法了。
算法
1算法的基本概念
1.1概念
计算机程序 = 数据结构 + 算法
算法就是对解决问题的方案准确而完整的描述，也就是描述如何解决问题的
1.2算法的评定标准
（1）算法的时间消耗（重点）
主要描述算法的时间消耗和问题规模之间的函数关系
（2）空间复杂度
主要描述算法的空间消耗和问题规模之间的函数关系
（3）正确性
主要描述算法的执行结果是否正确，是否满足要求
（4）可读性
主要描述算法的思想和流程是否容易阅读
（5）健壮性
主要描述算法对非正常输入的反应和处理能力（用户体验度）
1.3算法的描述形式
自然语言（注释）、伪代码（如：if（二叉树为空）{ }）、流程图、PAD图
2查找算法
2.1线性查找算法（顺序查找算法）
（1）算法流程
使用目标元素与一组数列中的每一个元素依次进行比较，直到查找成功，或者与所有的元素比较完毕，表示查找失败
（2）算法评价
平均时间复杂度 O（N）——–“O”表示时间复杂度——–“N”表示数据的个数
对样本的有序性不敏感
2.2二分查找算法（折半查找算法）
（1）算法流程
假设样本数据从小到大依次排列，首先选择中间元素进行比较，如果相等直接返回，表示查找成功；如果目标元素大于中间元素，则去中间元素的右侧查找，如果目标元素小于中间元素，则去中间元素的左侧查找，重复以上过程，直到找到满足条件的元素表示查找成功，或者没有找到，表示查找失败
（2）算法评价
平均时间复杂度 O（logN）
要求样本必须有序
3常见的排序算法
3.1冒泡排序算法
比较相邻位置的元素
（1）算法流程
a.比较相邻位置的元素，如果第一个比第二个大，则交换两个元素的位置
b.对每一对相邻位置的元素做同样的工作，从开始的第一对一直到最后一对，经过这一步，最后的元素将是这组元素中的最大值
c.针对所有的元素重复以上步骤，除了最后一个元素
d.持续对越来越少的元素重复以上步骤，直到没有元素需要交换为止
（2）算法评价
平均时间复杂度 O（N^2）,稳定，对样本的有序性非常敏感
3.2插入排序算法
（1）算法流程
斗地主 抓扑克牌
a.假定第一个元素已经有序
b.从第二个元素起依次取出，使用取出的元素依次和左边的元素进行比较，如果左边的元素大于取出的元素，则左边的元素右移
d。如果左边的元素小于取出的元素，或者左边已经没有元素，则将取出的元素插入到左边元素的右边，或者插入到最左边
e.重复步骤二，直到处理完毕所有的元素为止
（2）算法评价
平均时间复杂度O(N^2),稳定，对样本的有序性非常敏感，但是赋值的次数比冒泡排序少，因此略优于冒泡排序
3.3选择排序算法
（1）算法流程
a.从第一个元素起依次取出，并假定该元素是最小值，使用变量min记录该元素的下标
b.使用min记录的元素与后面的元素依次比较，如果找到了比min记录的元素还小的元素，则使用min记录更小的元素
c.直到使用min记录的元素与后续所有元素比较完毕，此时使用min记录的最小值和最开始假定的最小值交换位置，经过这一步，第一个元素已经是最小的
d.重复以上过程，直到所有元素有序为止
（2）算法评价
平均时间复杂度O(N^2),不稳定，对样本的有序性不敏感，虽然比较的次数多，但是交换的次数比较少，因此一般情况下略优于冒泡排序
4.快速排序算法
（1）算法流程
a.从样本元素中选择中间元素作为基准值
b.重组样本顺序，将所有比基准值小的元素放在基准值的左边，将所有比基准值大和相等的元素放在基准值的右边，这个过程叫做分组
c.以递归的方式对小于基准值的分组和大于基准值的分组分别重复 上述过程进行再分组排序，直到所有元素有序
（2）算法评价
平均时间复杂度O(NlogN)，不稳定，如果每次分组都能做到均匀分组，则排序速度最快
数据结构和算法
举例：
好了今天要和大家讨论的就是如何比较数字的大小，例如 0,1,2,3,4,5,6,7,8,9；这10个数，我们一眼就可以看出这是从小到大排列的，但是假如我给你这样几个数你给我从小到大排列出来：11,53,42,66,21,35,64,43,58,67；
你看到上面这几个数你会如何将他们排列出来呢？计算机所执行的任务，其实和我们人脑是一样的，但是他是按照我们所制定出来的规则进行判断的。所以我们只需要将我们是如何进行判断的过程用C语言表述出来就可以了。
我们知道11是上面数据中最小的那个数，可是你是怎么知道11是最小的呢？因为在你看到这些数据时，你已经在大脑中将11和其他所有的数据都比较了一遍才得出11是最小的那个数，所以我们写C语言程序时也要将11依次和其他的数比较一次。接下来第二位数应该是什么呢？我这么问你，你就应该快速的去进行比较，发现42比53小，所以53不是；接下来是66，而66比42大，所以66也不是；再接下来是21,21比42小，所以42不是,；然后是35，35比21小，所以35不是；。。。。。。就是这样依次比较，我们得出21是第二位数。用同样的方法我们可以得出接下来的数据， 最终我们排列出的数据是：11,21,35,42,43,53,58,64,66,67。
而接下来我们要做的就是将上面的执行过程用C语言表述出来：
void main(void)
{
int bubble[10] = {11,53,42,66,21,35,64,43,58,67}； //声明我们要排序的数组
int m = 0; //声明一个中间变量，用来保存要交换的数据
for(int i = 0; i
{
for(int j = i + 1;j
{
if(bubble[i] > bubble[j]) //如果当前的数比后面的数据大，则交换二者的位置
{
m = bubble[i]; //m就是用来保存中间数据的作用
bubble[i] = bubble[j];
bubble[j] = m;
}
}
}
}
上面的算法是每次比较出最小的一个数据并排列，就像是气泡从水里向上冒出一样，所以也叫冒泡排序。
当然，冒泡排序所花费的步骤较多，所以时间也花费的较多，并不是最好的排序算法，如果数组很大，那延时感就很明显，大家可以试着编写一下。
接下来还有插入排序、选择排序和快速排序，其中快速排序较难理解，这是一种不是特别稳定的排序法，它的执行时间受到分配方法的制约。大家可以先思考一下，里面有用到递归函数。
C
递归函数：
一个函数在它的函数体内调用它自身称为递归调用。这种函数称为递归函数。Ｃ语言允许函数的递归调用。在递归调用中，主调函数又是被调函数。执行递归函数将反复调用其自身，每调用一次就进入新的一层。
int f(int x)
{
int y;
z=f(y);
return z;
}
这个函数是一个递归函数。但是运行该函数将无休止地调用其自身，这当然是不正确的。为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。（摘自谭浩强C语言设计第三版）
例如用递归法计算 n!
用递归法计算 n!可用下述公式表示：
n!=1 (n=0,1)
n×(n-1)! (n>1)
按公式可编程如下：
long f(int n) //定义函数f,传递参数n;
{
long m; //定义参数m
if(n
else if(n==0||n==1) m=1; //否则判断n是否为0或者1，令m = 1
else m=f(n-1)*n; //（如果都不是上述条件，则m = f(n – 1) * n;就是这里函数f自己调用了自己，只是传递的参数变成了n-1;其实就是这样假设一开始传递的n等于10，运行到这里就是m = f(9) * 10;可是f(9)也要执行函数，那就变成了m =( f(8) * 9) *10;同样f(8)也要执行，就变成了m = (f(7) * 8 * 9 * 10);这样依次循环到f(1)时，f(1)就等于1，不会再有函数f出现了，这是函数执行的是1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10;）
return(m); //最好返回m;
}
以上的函数就是递归，其实我个人觉得函数有点难理解，很绕。但是他的功能还是非常强大的，大家可以试着去理解一下。
如著名的汉诺塔问题就可以用递归的思想去解决：
一块板上有三根针，A，B，C。A 针上套有 64 个大小不等的圆盘，大的在下，小的在上。如下图所示。要把这 64 个圆盘从 A 针移动 C 针上，每次只能移动一个圆盘，移动可以借助 B 针进行。但在任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上。求移动的步骤。
汉诺塔
这是一个典型的递归问题，大家可以先试着思考一下，步骤如下：
本题算法分析如下，设 A 上有 n 个盘子。
如果 n=1，则将圆盘从 A 直接移动到 C。
如果 n=2，则：
1.将 A 上的 n-1(等于 1)个圆盘移到 B 上；
2.再将 A 上的一个圆盘移到 C 上；
3.最后将 B 上的 n-1(等于 1)个圆盘移到 C 上。
如果 n=3，则：
A. 将 A 上的 n-1(等于 2，令其为 n`)个圆盘移到 B(借助于 C)，步骤如下：
(1)将 A 上的 n`-1(等于 1)个圆盘移到 C 上。
(2)将 A 上的一个圆盘移到 B。
(3)将 C 上的 n`-1(等于 1)个圆盘移到 B。
B. 将 A 上的一个圆盘移到 C。
C. 将 B 上的 n-1(等于 2，令其为 n`)个圆盘移到 C(借助 A)，步骤如下：
(1)将 B 上的 n`-1(等于 1)个圆盘移到 A。
(2)将 B 上的一个盘子移到 C。
(3)将 A 上的 n`-1(等于 1)个圆盘移到 C。
到此，完成了三个圆盘的移动过程。
从上面分析可以看出，当 n 大于等于 2 时，移动的过程可分解为三个步骤：
第一步 把 A 上的 n-1 个圆盘移到 B 上；
第二步 把 A 上的一个圆盘移到 C 上；
第三步 把 B 上的 n-1 个圆盘移到 C 上；其中第一步和第三步是类同的。
当 n=3 时，第一步和第三步又分解为类同的三步，即把 n`-1 个圆盘从一个针移到另一
个针上，这里的 n`=n-1。 显然这是一个递归过程，据此算法可编程如下：
move(int n,int x,int y,int z)
{
if(n==1)
printf(“%c–>%\n”,x,z);
else
{
move(n-1,x,z,y);
printf(“%c–>%\n”,x,z);
move(n-1,y,x,z);
}
}
main()
{
int h;
printf(\input number\n”);
scanf(“%d”,&h);
printf(“the step to moving %2d diskes\n”,h);
move(h,’a’,’b’,’c’);
}
想象力
今天讲述上面的内容其实并不是想要传递多少知识，只是想告诉大家，在编程时一定要“好学”更要“好奇”，优秀的算法都是来自大胆的想象和实验，所以希望大家能够开发自己的想象力，只有这样你才能成为正真的大牛！
