算法是一个程序和软件的灵魂，要成为一名优秀的程序员，只有对基础算法全面掌握，才能在设计程序和编写代码的过程中显得得心应手。
在我们学习C语言的过程中，我们除了语法基础，接触最多的就是各种各样的算法，同时算法也是我们考试的重中之重，可以说学好以下这些基础算法，我们离成功就又进了一步。
查找算法
一、顺序查找
基本思路：
遍历所有的元素，直到找到指定元素，返回下标。
必要条件：
数组可以是无序也可以是有序，没有特别的条件限制。
代码实现：
#include <stdio.h>
int search(int *a, int length, int num); //函数原型
int main() {
int a[10] = {3, 6, 2, 9, 10, 47, 27, 49, 25, 83}; //被查找的数组
int num = 27; //需要查找的元素
int length = (sizeof a) / (sizeof a[0]); //计算数组长度
printf("%d\n", search(a, length ,num));
return 0;
}
int search(int *a,int length, int num) {
int i;
for (i = 0; i < length; i++) { //遍历所有元素
if (a[i] == num) {
break;
}
}
if (i < length) {
return i; //如果找到就返回下标
}
return -1; //如果找不到就返回-1
}
// ----------02.21 - 18:19----------
//-----***-----Coding by QCQCQC-----***-----
输出结果：
6
注意事项：
- 在C中获取数组长度需要用到sizeof关键字
- 在函数中不能直接传递数组，本质上传递的是数组的指针
二、二分查找
基本思路：
在有序表中，每次都取中间元素作为比较的对象。
如果给中间值与给定值相等，则查找成功，返回该元素的下标/索引；
如果中间值大于给定值，则在中间值的右半区间继续查找；
如果中间值小于给定值，则在中间值的左半区间继续查找；
确定了该元素所在范围那么范围外的元素就不需要查找了，不断重复上诉过程，直至找到
二分查找每次查找都可以排除剩余元素的一半，所以相比顺序查找的查找效率提高了很多。
必要条件：
- 数组元素必须有序
- 每次查找的元素只能是一个
详细图解：
这里对比二分查找（上）与顺序查找（下）
如何构建二叉查找树：
二叉查找树的应用：
代码实现：
int Find(int arr[], int n, int key){ //查找指定元素所在位置
for(int i=0; i<n; ++i){
if(arr[i] == key)
//如果指定元素key与数组中的某元素arr[i]相等，则返回它的下标i
return i;
}
return -1; //否则返回-1，表示未查找到与它相等的元素
}
//二分法查找指定元素所在位置（前提条件是先按从小到大进行排列）
int BinarySearch1(int arr[], int size, int key) {
int low = 0; //设置低下标
int high = size-1; //设置高下标
int mid;
while(low <= high){ //一旦高下标小于低下标结束while循环
mid = low+(high-low)>>1; //设置中间下标(右移一位相当于/2)
if(key < arr[mid]) //如果指定元素比中间下标的值小
high = mid-1; //则把中间下标-1给高下标
else if(key > arr[mid]) //如果指定元素比中间下标的值大
low = mid+1; //则把中间下标+1给低下标
else //否则返回 中间下标
return mid;
}
return -1; //返回-1则表示在该数组中未找到该指定元素
}
注意事项：
二分查找最重要的两个点，就是循环条件和后续的区间赋值问题
1.while 中的循环条件：left < right 还是 left <= right
2.对于右侧边界的处理：right = middle 还是 right =middle-1左闭右闭区间，查找区间为[left,right]
左闭右开区间，查找区间为[left,right）
三、插值查找 / 斐波那契查找
基本思路：
在二分查找的基础上提高查找效率。
必要条件：
与二分查找相同，要求数据有序
代码实现：
将二分查找的mid计算方式稍加修改：
插值查找：
mid = left + (num - arr[left])/(arr[right] - arr[left])*(right-left);
斐波那契查找:
mid = min + ( right - left ) * 0.618 -1; //使用到了黄金分割
排序算法
一、冒泡排序
基本思路：
每次将相邻的两个数比较，将小的调在前面。
最大的数沉到了最底下成为了最下面的一个数，而小的数“上升”。
必要条件：
没有特别的条件要求，但原数组越接近结果，排序效率越高。
详细图解：
代码实现：
#include <stdio.h>
int main(void) {
int a[10] = {6, 4, 3, 2, 7, 8, 9, 10, 1, 5};
int i, k, w;
for (i = 0; i < 9; i++) {
for (k = 0; k < 9 - i; k++) {
if (a[k] > a[k + 1]) {
w = a[k];
a[k] = a[k + 1];
a[k + 1] = w;
}
}
}
for (i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
}
// ----------02.21 - 18:40----------
//-----***-----Coding by QCQCQC-----***-----
注意事项：
最外层循环不能覆盖全部的范围，否则会产生越界。（结果不可控）
在每一轮比较完成后，下一轮比较都会比上一轮减少一个，那么第i轮比较就会比上一轮减少i个，i就是外循环的轮次。
如果比较数中有相同或者实行一次冒泡排序后，数值没有变化，那么说明数组已经有序，我们可以有加入一个标记flag，来避免多余的比较，即现在循环前加入flag=0，如果这一轮排序了就令flag为1，否则flag为0，即这一回合没排序，跳出循环。
for (i = 0; i < n - 1; i++){ //确定排序趟数
int flag = 0;
for (j = 0; j < n - 1 - i; j++){ //确定每轮比较次数
if (a[j]>a[j + 1]){
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
flag=1; //如果发生交换，则进行标记
}
}
if(!flag)
break;
}
二、插入排序
基本思路：
将数据按照一定的顺序一个一个的插入到有序的表中，最终得到的序列就是已经排序好的数据。
必要条件：
没有特别的条件要求，但原数组越接近结果，排序效率越高。
详细图解：
代码实现：
void Insert_sort(int *ar,int len)//插入排序默认步长为1，使用于小量级序列
{
int temp = 0;
int i = 0,j = 0;
for(i = 1;i < len;i++){//第一个循环，插入排序是从第二个元素开始排序的，所以此处的i = 1
if(ar[i] < ar[i - 1]){//限定条件：后面的元素小于前面的元素
temp = ar[i];//利用临时变量保存后面的元素
for(j = i - 1;j >= 0 && ar[j] > temp;j--){//这层循环是为了检查前面已经排序好的元素，循环执行的条件就是j下标不会低于0下标且前面已经排序好的元素出现了比临时变量更大的元素。
ar[j + 1] = ar[j];//将前面已经排序好的元素统一向后迁移一位
}
ar[j + 1] = temp;//将temp中存放的值赋值给需要插入的位置上
}
}
}
注意事项：
插入排序时，将无序数据取出，在有序区内查找插入位置，完成插入后有序区位置扩大，无序区位置减小。
三、选择排序
基本思路：
选择排序的思路跟我们生活十分贴近，从一组数中扫一眼，找到最小的，放到最左边，第二小的放在左起第二个，以此类推！
详细图解：
代码实现：
#include <stdio.h>
int main(void) {
int a[10] = {6, 1, 4, 5, 7, 8, 9, 2, 3, 10};
int i, k, pos;
for (i = 0; i < 10; i++) {
pos = i;
for (k = i + 1; k < 10; k++) {
if (a[k] < a[pos]) {
pos = k;
}
}
if (pos != i) {
int c;
c = a[i];
a[i] = a[pos];
a[pos] = c;
}
}
for (i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
}// ----------02.21 - 18:56----------
//-----***-----Coding by QCQCQC-----***-----
注意事项：
选择排序中，最理想的状况就是移动次数为0次，原来就是一组有序数，最复杂的情况就是一组倒序数，最小的数字在最后面，最多要移动3(n-1)次，6个数字就要移动30次。时间复杂度为O(n²)。
四、快速排序
什么是快速排序？
快速排序算法是在几种排序算法中效率最高的一个排序算法了，故称为快速排序，它的时间复杂度为：O(nlog2n)，相比冒泡排序算法的O(n2)有很大的提升。
基本思路：
1、选取一个基准元素(一般我们将待排序序列中的第一个元素选取为基准元素)
2、将其他元素与基准元素进行比较，比基准元素大的放到基准元素的右边，比基准元素小的放到基准元素的右边。(以基准元素为中心将元素重新分成两个序列，并返回基准元素的下标)
3、将新生成的两个序列继续执行1和2两步(此处可以用递归实现)
详细图解：
我们有一个待排序序列是：【 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48】
第一轮排序：
①选取第一个元素44为基准坐标。
②以44为中心，将序列分为两部分，左边比44小，右边比44大。
③原来的序列被分成两部分，一部分比44小的是【0，基准坐标-1】，另一部分比44大的是【基准坐标+1，最后】，将这两部分继续执行①和②两步最终即可排序完成。
第一轮排序总结： 算法思想其实不难理解，那么接下来需要解决的问题就是，如何将一个序列以基准坐标分成相对有序的两部分，以及递归出口问题。
算法分析：
1.时间复杂度
O(nlog2n)
2.空间复杂度
空间复杂度由于需要开辟一个临时空间来存储基准坐标所以是：O(1)
代码实现：
#include<stdio.h>
void Print(int array[],int len){
for(int i=0;i<len;i++){
printf("%d ",array[i]);
}
printf("\n");
}
/*获取基准坐标，并相对有序(左边比基准坐标小，右边比基准坐标大)*/
int getStandard(int array[],int low,int high) {
int key = array[low]; //临时保存基准元素
while(low<high) {
//high指针从后向前遍历 ， 元素比基准元素大则指针向前移动 则比基准元素小则和基准元素交换
while(low<high && array[high]>=key){
high--;
}
if(low<high){
array[low] = array[high]; //赋值给第一个元素，因为第一个元素作为基准元素已经临时保存了，所可以直接赋值
}
//low指针从前向后遍历 ， 元素比基准元素小则指针向后移动 否则比基准元素大则和基准元素交换
while(low<high && array[low]<=key){
low++;
}
if(low<high){
array[high] = array[low]; //复制给high指针所指得位置，因为在11行已经赋值给array[low]了
}
}
array[low] = key;
return low;
}
void QuickSort(int array[],int low,int high){
if(low<high){ //递归出口
int standard = getStandard(array,low,high);
QuickSort(array,low,standard-1); //比基准元素小的部分继续调用快速排序
QuickSort(array,standard+1,high); //比基准元素大的部分继续调用快速排序
}
}
int main(){
int array[] = {3, 44, 38, 5, 47, 15, 36};
int size = sizeof(array) / sizeof(int);
printf("原始序列为：\n");
Print(array,size);
QuickSort(array,0,size-1);
printf("排序后序列为：\n");
Print(array,size);
}
总结：
在快速排序中我们遇到了递归的算法思想，将代码块分为比基础元素大的部分和小的部分，对两部分继续进行“递”的操作，直到完成排序，“归”回最初的调用处，整体的排序也随之完成。