如下冒泡排序例子

#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");//结束不退出 }3、二分查找算法

二分査找就是折半查找，

其基本思想是：首先选取表中间位置的记录，将其关键字与给定关键字 key 进行比较，若相等，则査找成功；

若 key 值比该关键字值大，则要找的元素一定在右子表中，则继续对右子表进行折半查找；

若 key 值比该关键宇值小，则要找的元素一定在左子表中，继续对左子表进行折半査找。

如此递推，直到査找成功或査找失败（或査找范围为 0）。

例如：

要求用户输入数组长度，也就是有序表的数据长度，并输入数组元素和査找的关键字。

程序输出查找成功与否，以及成功时关键字在数组中的位置。

例如，在有序表 11、13、18、 28、39、56、69、89、98、122 中査找关键字为 89 的元素。

#define _CRT_SECURE_NO_WARNINGS //避免scanf报错 #include <stdio.h> int binary_search(int key, int a[], int n) //自定义函数binary_search() { int low, high, mid, count = 0, count1 = 0; low = 0; high = n - 1; while (low<high) //査找范围不为0时执行循环体语句 { count ; //count记录査找次数 mid = (low high) / 2; //求中间位置 if (key<a[mid]) //key小于中间值时 high = mid - 1; //确定左子表范围 else if (key>a[mid]) //key 大于中间值时 low = mid 1; //确定右子表范围 else if (key == a[mid]) //当key等于中间值时，证明查找成功 { printf("查找成功!\n 查找 %d 次!a[%d]=%d", count, mid, key); //输出査找次数及所査找元素在数组中的位置 count1 ; //count1记录查找成功次数 break; } } if (count1 == 0) //判断是否查找失敗 printf("查找失敗!"); //査找失敗输出no found return 0; } int main() { int i, key, a[100], n; printf("请输入数组的长度：\n"); scanf("%d", &n); //输入数组元素个数 printf("请输入数组元素：\n"); for (i = 0; i<n; i ) scanf("%d", &a[i]); //输入有序数列到数组a中 printf("请输入你想查找的元素：\n"); scanf("%d", &key); //输入要^找的关键字 binary_search(key, a, n); //调用自定义函数 printf("\n"); system("PAUSE");//结束不退出; }

搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。

现阶段一般有枚举算法、深度优先搜索、广度优先搜索、A*算法、回溯算法、蒙特卡洛树搜索、散列函数等算法。

在大规模实验环境中，通常通过在搜索前，根据条件降低搜索规模；

根据问题的约束条件进行剪枝；利用搜索过程中的中间解，避免重复计算这几种方法进行优化。

这里介绍的是深度优先搜索，感兴趣的可以百度查询更多搜索算法。

内容很多，大家可以百度查询感兴趣的用法：也可以点击 深度优先搜索 查看更多。

深度优先搜索

• 深度优先遍历首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点均已被访问为止。
• 若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

深度搜索与广度搜索的相近，最终都要扩展一个结点的所有子结点.

　　区别在于对扩展结点过程，深度搜索扩展的是E-结点的邻接结点中的一个，并将其作为新的E-结点继续扩展，当前E-结点仍为活结点，待搜索完其子结点后，回溯到该结点扩展它的其它未搜索的邻接结点。

而广度搜索，则是扩展E-结点的所有邻接结点，E-结点就成为一个死结点。

1. 什么是哈希

Hash，一般翻译做散列、杂凑，或音译为哈希，是一个典型的利用空间换取时间的算法，把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。

如有一个学生信息表：

学生的学号为：年纪 学院号 班级号 顺序排序号【如：19(年纪) 002(2号学院) 01(一班) 17(17号)---à190020117】类似于一个这样的信息，

当我们需要找到这个学号为【190020117】的学生，在不适用哈希的时候，我们通常是使用一个顺序遍历的方式在数据中进行查询大类，再查询子类得到，

这样的作法很明显不够快 ，需要O(n)左右的时间花费，对于大型的数据规模而言这显然不行，

而哈希的做法是，根据一定的规律(比如说年纪不存在过老和过小的情况，以此将【190020117】进行压缩成一个简短的数据如：

【192117】)并且将这个数据直接作用于内存的地址，届时我们查询【190020117】只需要进行一次压缩并访问【192117】这个地址即可，而这个压缩的方法（函数），就可以称之为哈希函数。

一般的对于哈希函数需要考虑如下内容:

1. 计算散列地址所需要的时间（即hash函数本身不要太复杂）
2. 关键字的长度
3. 表长(不宜过长或过短，避免内存浪费和算力消耗)
4. 关键字分布是否均匀，是否有规律可循
5. 设计的hash函数在满足以上条件的情况下尽量减少冲突

2.哈希与哈希表

在理解了哈希的思维之后，我们要了解什么是哈希表，哈希表顾名思义就是经过哈希函数进行转换后的一张表，

通过访问哈希表，我们可以快速查询哈希表，从而得出所需要得到的数据，构建哈希表的核心就是要考虑哈希函数的冲突处理（即经过数据压缩之后可能存在多数据同一个地址，需要利用算法将冲突的数据分别存储）。

冲突处理的方法有很多，最简单的有 1法，即地址数直接 1，当两个数据都需要存储进【2019】时，可以考虑将其中的一个存进【2020】

此外还有，开放定址法，链式地址发，公共溢出法，再散列法，质数法等等，各方法面对不同的数据特征有不同的效果。

3.哈希的思维

Hash算法是一个广义的算法，也可以认为是一种思想，使用Hash算法可以提高存储空间的利用率，可以提高数据的查询效率，也可以做数字签名来保障数据传递的安全性。

所以Hash算法被广泛地应用在互联网应用中。

比如，利用哈希的思维在O(1)的复杂度情况下任意查询1000以内所有的质数（在创建是否是质数的时候并不是O(1)的复杂度），

注意本样例只是演示思维，面对本需求可以有更好的空间利用方式（本写法比较浪费空间，仅供了解）。

如下例子：

【电话聊天狂人】

给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。

输入格式:
输入首先给出正整数N（≤105​），为通话记录条数。随后N行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。

输出格式:
在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。
输入样例：

4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832

输出样例：

13588625832 3

#define _CRT_SECURE_NO_WARNINGS //避免scanf报错 #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #include <ctype.h> #define MAX 400000 /** 定义 最大 数组 大小 **///（感觉没啥用 但是最好尽可能开大点，但是不要太大，不要超出系统可建造范围） typedef struct Node *Hash; /**新的路程又开始了 这次准备用数组来做哈希 还有双向平方处理冲突**/ struct Node{ char phone[15]; int num; }; int maxInt(int x, int y) { if (x>y) return x; else return y; } char* minstr(char *x, char *y) { if (strcmp(x, y)>0) return y; else return x; } int nextprime(const int n) { int p = (n % 2 == 1) ? n 2 : n 1; /**先找一个大于N的奇数**/ int i; while (p<MAX) { for (i = (int)sqrt(p); i >= 2; i--) /**然后再判断是不是素数**/ if (p%i == 0) break; if (i<2) return p; /**是 那就返回这个数**/ else p = 2;/**不是 那就下一个奇数**/ } } int deal(char *s, int p) /**然后把字符串映射成下标 (映射的方式很多很多，随便猜一个靠谱的就行了)**/ { int index = (atoi(s 2)) % p; return index; } int insert(Hash h, int pos, char *s, int p, int Max) /**哈希查找的插入实现 ,分别是哈希数组，数组位置，身份证号，数组最大大小, MAX 看到代码最后就明白了**/ { int i, posb = pos; /**备份pos值方便双向平方查找**/ for (i = 1;; i ) { if (strcmp(h[pos].phone, "") == 0) /**如果为pos的值空直接插入**/ { strcpy(h[pos].phone, s); h[pos].num ; Max = max(Max, h[pos].num); break; } else { if (strcmp(h[pos].phone, s) == 0) /**不为空的话，就看看身份证号是不是想等**/ { h[pos].num ; Max = maxInt(Max, h[pos].num); break; } else { //原p%2==1 if (i % 2 == 1) pos = (posb (i*i)) % p; /**不相等 就找下一个位置 ，分别向后找一次和往前找一次，如此循环**/ else { //原i*i pos = posb - ((i - 1)*(i - 1)); while (pos<0) pos = p; } } } } return Max; } void initial(Hash h, int p) /**把哈希数组初始化 （初始化的动词英文忘记咋写了。。。。）**/ { int i; for (i = 0; i<p; i ) { h[i].phone[0] = '\0'; h[i].num = 0; } } int main(){ int Max = 0; int n; /**总数 N 然后就开始找 大于N的最小素数了**/ scanf("%d", &n); /**输出中把\n也输入进去 避免下面输入会出现奇葩的事情**/ int p = nextprime(2 * n); /**突然想起来 每次输入的都是俩电话号码，所以 电话号码最大数是2*n**/ Hash h = (Hash)malloc(p*sizeof(struct Node));/**建立哈希数组**/ initial(h, p); char phone[15]; char phone1[15]; while (n--) { scanf("%s %s", phone, phone1); Max = insert(h, deal(phone, p), phone, p, Max); Max = insert(h, deal(phone1, p), phone1, p, Max); } int i, num = 0; char *Minstr = NULL; for (i = 0; i<p; i ) { if (h[i].num == Max) { if (Minstr == NULL) Minstr = h[i].phone; else Minstr = minstr(Minstr, h[i].phone); num ; } } printf("%s %d", Minstr, Max); if (num>1) printf(" %d", num); system("PAUSE");//结束不退出 }6、贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件，直到把所有数据枚举完。

贪心算法的思想如下：

1. 建立数学模型来描述问题；
2. 把求解的问题分成若干个子问题；
3. 对每一子问题求解，得到子问题的局部最优解；
4. 把子问题的解局部最优解合成原来解问题的一个解。

与动态规划不同的是，贪心算法得到的是一个局部最优解（即有可能不是最理想的），而动态规划算法得到的是一个全局最优解（即必须是整体而言最理想的），

一个有趣的事情是，动态规划中的01背包问题就是一个典型的贪心算法问题。

如下例子：贪心算法货币统计问题

#define _CRT_SECURE_NO_WARNINGS //避免scanf报错 #include <stdio.h> #include <malloc.h> void main() { int i, j, m, n, *ns = NULL, *cn = NULL, sum = 0; printf("请输入总金额m及零钱种类n："), scanf("%d", &m), scanf("%d", &n); printf("请分别输入%d种零钱的面额：\n", n); if (!(ns = (int *)malloc(sizeof(int)*n))) return 1; if (!(cn = (int *)malloc(sizeof(int)*n))) return 1; for (i = 0; i<n; i ) scanf("%d", &ns[i]); //------------考虑输入面额顺序不定，先对面额进行降序排列（如按照降序输入，该段可删除） for (i = 0; i<n; i ) for (j = i 1; j<n; j ) if (ns[j]>ns[i]) ns[j] ^= ns[i], ns[i] ^= ns[j], ns[j] ^= ns[i]; for (i = 0; i<n; i )//贪心算法，从最大面额开始 if (m >= ns[i]) cn[i] = m / ns[i], m = m%ns[i], sum = cn[i], printf("%d元%d张 ", ns[i], cn[i]); printf("\n最少使用零钱%d张\n", sum); system("PAUSE");//结束不退出 }

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。

求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

复杂度为 O(lgn)O(lg⁡n) 的分治算法

#define _CRT_SECURE_NO_WARNINGS //避免scanf报错 #include "stdio.h" #include "stdlib.h" int power(int x, int n) { int result; if (n == 1) return x; if (n % 2 == 0) result = power(x, n / 2) * power(x, n / 2); else result = power(x, (n 1) / 2) * power(x, (n - 1) / 2); return result; } void main() { int x = 5; int n = 3; printf("power(%d,%d) = %d \n", x, n, power(x, n)); system("PAUSE");//结束不退出 }归并排序

时间复杂度是O(NlogN)O(Nlog⁡N)，空间复制度为O(N)O(N)（归并排序的最大缺陷）
归并排序（Merge Sort）完全遵循上述分治法三个步骤：

1. 分解：将要排序的n个元素的序列分解成两个具有n/2个元素的子序列；
2. 解决：使用归并排序分别递归地排序两个子序列；
3. 合并：合并两个已排序的子序列，产生原问题的解。

#define _CRT_SECURE_NO_WARNINGS //避免scanf报错 #include "stdio.h" #include "stdlib.h" #include "assert.h" #include "string.h" void print_arr(int *arr, int len) { int i = 0; for (i = 0; i < len; i ) printf("%d ", arr[i]); printf("\n"); } void merge(int *arr, int low, int mid, int hight, int *tmp) { assert(arr && low >= 0 && low <= mid && mid <= hight); int i = low; int j = mid 1; int index = 0; while (i <= mid && j <= hight) { if (arr[i] <= arr[j]) tmp[index ] = arr[i ]; else tmp[index ] = arr[j ]; } while (i <= mid) //拷贝剩下的左半部分 tmp[index ] = arr[i ]; while (j <= hight) //拷贝剩下的右半部分 tmp[index ] = arr[j ]; memcpy((void *)(arr low), (void *)tmp, (hight - low 1) * sizeof(int)); } void mergesort(int *arr, int low, int hight, int *tmp) { assert(arr && low >= 0); int mid; if (low < hight) { mid = (hight low) >> 1; mergesort(arr, low, mid, tmp); mergesort(arr, mid 1, hight, tmp); merge(arr, low, mid, hight, tmp); } } //只分配一次内存，避免内存操作开销 void mergesort_drive(int *arr, int len) { int *tmp = (int *)malloc(len * sizeof(int)); if (!tmp) { printf("out of memory\n"); exit(0); } mergesort(arr, 0, len - 1, tmp); free(tmp); } void main() { int data[10] = { 8, 7, 2, 6, 9, 10, 3, 4, 5, 1 }; int len = sizeof(data) / sizeof(data[0]); mergesort_drive(data, len); print_arr(data, len); system("PAUSE");//结束不退出 }

还有更多例子可以百度，这里就不一一举例了。

回溯算法，又称为“试探法”。解决问题时，每进行一步，都是抱着试试看的态度，如果发现当前选择并不是最好的，或者这么走下去肯定达不到目标，立刻做回退操作重新选择。

这种走不通就回退再走的方法就是回溯算法。

例如，在解决列举集合 {1,2,3} 中所有子集的问题中，就可以使用回溯算法。

从集合的开头元素开始，对每个元素都有两种选择：取还是舍。当确定了一个元素的取舍之后，再进行下一个元素，直到集合最后一个元素。

其中的每个操作都可以看作是一次尝试，每次尝试都可以得出一个结果。将得到的结果综合起来，就是集合的所有子集。

#define _CRT_SECURE_NO_WARNINGS //避免scanf报错 #include <stdio.h> //设置一个数组，数组的下标表示集合中的元素，所以数组只用下标为1，2，3的空间 int set[5]; //i代表数组下标，n表示集合中最大的元素值 void PowerSet(int i, int n){ //当i>n时，说明集合中所有的元素都做了选择，开始判断 if (i>n) { for (int j = 1; j <= n; j ) { //如果树组中存放的是 1，说明在当初尝试时，选择取该元素，即对应的数组下标，所以，可以输出 if (set[j] == 1) { printf("%d ", j); } } printf("\n"); } else{ //如果选择要该元素，对应的数组单元中赋值为1；反之，赋值为0。然后继续向下探索 set[i] = 1; PowerSet(i 1, n); set[i] = 0; PowerSet(i 1, n); } } void main() { int n = 3; for (int i = 0; i<5; i ) { set[i] = 0; } PowerSet(1, n); system("PAUSE");//结束不退出 }