上一章我们说了常见的10种数据结构，接下来我们说常见的10种算法。
上一章地址：基础夯实：基础数据结构与算法(一)，不怎么清楚的可以去瞅瞅。
常见的10种算法
数据结构研究的内容：就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。
算法研究的目的是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。
一般有以下几种常用运算：
- 检索：检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。
- 插入：往数据结构中增加新的节点。
- 删除：把指定的结点从数据结构中去掉。
- 更新：改变指定节点的一个或多个字段的值。
- 排序：把节点按某种指定的顺序重新排列。例如递增或递减。
1、递归算法
递归算法：是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
递归过程一般通过函数或子过程来实现。
递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。
递归算法解决问题的特点：
- 递归就是在过程或函数里调用自身。
- 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
- 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
- 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。
下面来详细分析递归的工作原理。
先看看C语言中函数的执行方式，需要了解一些关于C程序在内存中的组织方式：
堆的增长方向为从低地址到高地址向上增长，而栈的增长方向刚好相反（实际情况与CPU的体系结构有关）。
当C程序中调用了一个函数时，栈中会分配一块空间来保存与这个调用相关的信息，每一个调用都被当作是活跃的。
栈上的那块存储空间称为活跃记录或者栈帧。
栈帧由5个区域组成：输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数，参见下图：
栈是用来存储函数调用信息的绝好方案，然而栈也有一些缺点：
栈维护了每个函数调用的信息直到函数返回后才释放，这需要占用相当大的空间，尤其是在程序中使用了许多的递归调用的情况下。
除此之外，因为有大量的信息需要保存和恢复，因此生成和销毁活跃记录需要消耗一定的时间。
我们需要考虑采用迭代的方案。幸运的是我们可以采用一种称为尾递归的特殊递归方式来避免前面提到的这些缺点。
例题1：计算n！
计算n的阶乘，数学上的计算公式为：
n！=n×(n-1)×(n-2)……2×1
使用递归的方式，可以定义为：
以递归方式实现阶乘函数的实现：
#define _CRT_SECURE_NO_WARNINGS //避免scanf报错 #include <stdio.h> int main(void) { int sumInt = fact(3); printf("3的阶乘为：%d\n", sumInt); system("PAUSE");//结束不退出 } //递归求阶乘 int fact(int n) { if (n < 0) return 0; else if (n == 0 || n == 1) return 1; else return n * fact(n - 1); }
例题2：斐波那契数列
#define _CRT_SECURE_NO_WARNINGS //避免scanf报错 #include <stdio.h> void main(void) { printf("%d \n", fibonacci(10)); system("PAUSE");//结束不退出 } //斐波那契数列，第一二项为1；后面的每一项为前两项之和 int fibonacci(int a){ if (a == 1 || a == 2) { return 1; } else{ return fibonacci(a - 1) + fibonacci(a - 2); } }
例题3：递归将整形数字转换为字符串
#define _CRT_SECURE_NO_WARNINGS //避免scanf报错 #include <stdio.h> void main(void) { char str[100]; int i; printf("enter a integer:\n"); scanf("%d", &i); toString(i, str); puts(str); system("PAUSE");//结束不退出 } //递归将整形数字转换为字符串 int toString(int i, char str[]){ int j = 0; char c = i % 10 + '0'; if (i /= 10) { j = toString(i, str) + 1; } str[j] = c; str[j + 1] = '\0'; return j; }
例题4：汉诺塔
#define _CRT_SECURE_NO_WARNINGS //避免scanf报错 #include <stdio.h> //递归汉诺塔 void hanoi(int i, char x, char y, char z){ if (i == 1){ printf("%c -> %c\n", x, z); } else{ hanoi(i - 1, x, z, y); printf("%c -> %c\n", x, z); hanoi(i - 1, y, x, z); } } void main(void) { hanoi(10, 'A', 'B', 'C'); system("PAUSE");//结束不退出 }
例题5：猴子吃桃
#define _CRT_SECURE_NO_WARNINGS //避免scanf报错 #include <stdio.h> //猴子吃桃，每天吃一半再多吃一个，第十天想吃时候只剩一个 int chitao(int i){ if (i == 10){ return 1; } else{ return (chitao(i + 1) + 1) * 2; } } void main(void) { printf("%d", chitao(5)); system("PAUSE");//结束不退出 }
例题6：N皇后问题
#define _CRT_SECURE_NO_WARNINGS //避免scanf报错 #include <stdio.h> /*======================N皇后问题========================*/ #define N 100 int q[N];//列坐标 //输出结果 void dispasolution(int n) { static int count = 0; printf(" 第%d个解:", ++count); for (int i = 1; i <= n; i++) { printf("(%d,%d) ", i, q[i]); } printf("\n"); } //判断位置(i,j)能否放皇后 int place(int i, int j) { //第一个皇后总是可以放 if (i == 1) return 1; //其他皇后不能同行，不能同列，不能同对角线 int k = 1; //k~i-1是已经放置了皇后的行 while (k < i) { if ((q[k] == j) || (abs(q[k] - j) == abs(i - k))) return 0; k++; } return 1; } //放置皇后 void queen(int i, int n) { if (i > n)dispasolution(n); else { for (int j = 1; j <= n; j++) { if (place(i, j)==1) { q[i] = j; queen(i + 1, n); } } } } int main() { queen(1, 4); system("PAUSE");//结束不退出 }
2、排序算法
排序是程序设计中常做的操作，初学者往往只知道冒泡排序算法，其实还有很多效率更高的排序算法，比如希尔排序、快速排序、基数排序、归并排序等。
不同的排序算法，适用于不同的场景，本章最后从时间性能，算法稳定性等方面，分析各种排序算法。
排序算法，还分为内部排序算法和外部排序算法，之间的区别是，前者在内存中完成排序，而后者则需要借助外部存储器。
这里介绍的是内部排序算法。
冒泡排序：
起泡排序，别名“冒泡排序”，该算法的核心思想是将无序表中的所有记录，通过两两比较关键字，得出升序序列或者降序序列。
例如，对无序表{49，38，65，97，76，13，27，49}进行升序排序的具体实现过程如图 1 所示：
如下冒泡排序例子
#define _CRT_SECURE_NO_WARNINGS //避免scanf报错 #include <stdio.h> //冒泡排序 //交换 a 和 b 的位置的函数 void swap(int *a, int *b); void main() { int array[8] = { 49, 38, 65, 97, 76, 13, 27, 49 }; int i, j; int key; //有多少记录，就需要多少次冒泡，当比较过程，所有记录都按照升序排列时，排序结束 for (i = 0; i < 8; i++){ key = 0;//每次开始冒泡前，初始化 key 值为 0 //每次起泡从下标为 0 开始，到 8-i 结束 for (j = 0; j + 1<8 - i; j++){ if (array[j] > array[j + 1]){ key = 1; swap(&array[j], &array[j + 1]); } } //如果 key 值为 0，表明表中记录排序完成 if (key == 0) { break; } } for (i = 0; i < 8; i++){ printf("%d ", array[i]); } system("PAUSE");//结束不退出 } void swap(int *a, int *b){ int temp; temp = *a; *a = *b; *b = temp; }
快速排序：
快速排序算法是在起泡排序的基础上进行改进的一种算法，
其实现的基本思想是：通过一次排序将整个无序表分成相互独立的两部分，其中一部分中的数据都比另一部分中包含的数据的值小，然后继续沿用此方法分别对两部分进行同样的操作，
直到每一个小部分不可再分，所得到的整个序列就成为了有序序列。
该操作过程的具体实现代码为：
复制代码 #define _CRT_SECURE_NO_WARNINGS //避免scanf报错 #include <stdio.h> #include <stdlib.h> #define MAX 9 //单个记录的结构体 typedef struct { int key; }SqNote; //记录表的结构体 typedef struct { SqNote r[MAX]; int length; }SqList; //此方法中，存储记录的数组中，下标为 0 的位置时空着的，不放任何记录，记录从下标为 1 处开始依次存放 int Partition(SqList *L, int low, int high){ L->r[0] = L->r[low]; int pivotkey = L->r[low].key; //直到两指针相遇，程序结束 while (low<high) { //high指针左移，直至遇到比pivotkey值小的记录，指针停止移动 while (low<high && L->r[high].key >= pivotkey) { high--; } //直接将high指向的小于支点的记录移动到low指针的位置。 L->r[low] = L->r[high]; //low 指针右移，直至遇到比pivotkey值大的记录，指针停止移动 while (low<high && L->r[low].key <= pivotkey) { low++; } //直接将low指向的大于支点的记录移动到high指针的位置 L->r[high] = L->r[low]; } //将支点添加到准确的位置 L->r[low] = L->r[0]; return low; } void QSort(SqList *L, int low, int high){ if (low<high) { //找到支点的位置 int pivotloc = Partition(L, low, high); //对支点左侧的子表进行排序 QSort(L, low, pivotloc - 1); //对支点右侧的子表进行排序 QSort(L, pivotloc + 1, high); } } void QuickSort(SqList *L){ QSort(L, 1, L->length); } void main() { SqList * L = (SqList*)malloc(sizeof(SqList)); L->length = 8; L->r[1].key = 49; L->r[2].key = 38; L->r[3].key = 65; L->r[4].key = 97; L->r[5].key = 76; L->r[6].key = 13; L->r[7].key = 27; L->r[8].key = 49; QuickSort(L); for (int i = 1; i <= L->length; i++) { printf("%d ", L->r[i].key); } system("PAUSE");//结束不退出 }
更多点击 排序算法：http://data.biancheng.net/sort/ （插入排序算法、快速排序算法、选择排序算法、归并排序和基数排序等）
