本篇介绍一些C语言算法相关内容.
1. 算法的基本概念以及评价文章源自微观生活（93wg.com）微观生活-https://93wg.com/20083.html
1.1 基本概念文章源自微观生活（93wg.com）微观生活-https://93wg.com/20083.html
算法(Algorithm) 就是指对解题方案准确而又完全的描写， 是一系列解决问题的清晰指令.文章源自微观生活（93wg.com）微观生活-https://93wg.com/20083.html
1.2 评定标准文章源自微观生活（93wg.com）微观生活-https://93wg.com/20083.html
（1）时间繁杂度（重点关注)文章源自微观生活（93wg.com）微观生活-https://93wg.com/20083.html
-主要用于描写算法的时间损耗以及问题范围的函数关系， 常数级的时间繁杂度、 线性关系的时间繁杂度、 平方级的时间繁杂度...文章源自微观生活（93wg.com）微观生活-https://93wg.com/20083.html
（2）空间繁杂度文章源自微观生活（93wg.com）微观生活-https://93wg.com/20083.html
-主要用于描写算法的空间损耗以及问题范围的函数关系文章源自微观生活（93wg.com）微观生活-https://93wg.com/20083.html
（3）正确性文章源自微观生活（93wg.com）微观生活-https://93wg.com/20083.html
-主要用于描写算法的执行结果是不是知足请求文章源自微观生活（93wg.com）微观生活-https://93wg.com/20083.html
（4）可读性
-主要用于描写算法自身是不是便于人们的浏览
（5）健壮性
-主要用于描写算法对非正常输入的处理能力
1.3 算法的描写方式
目前主要的算法描写方式有： 自然语言、 伪代码、 流程节制图、 PAD 图... ...
2. 经常使用的查找算法
2.1 线性查找算法（ 顺序查找算法）
（1）算法流程
使用目标元素与样本数列中的第一个元素起顺次进行比较， 如果找到与目标元素相等的元素则表示查找胜利， 或者所有样本元素与目标元素都比较终了， 也没有相等的元素， 则表示查找失败
int Sequence_Search(int *array, int length, int key){ for(int i=0; i<length; ++i) { if(array[i] == key) return i; } return -1; }
（2）算法评价
平均时间繁杂度 O(N)， 不请求样本数列中的元素有序
2.2 二分查找算法（ 折半查找算法）
（1）算法流程
假设样本中的所有数列元素依照从小到大顺次排列， 使用目标元素与样本数列中的中间元素进行比较， 如果相等则查找胜利， 如果目标元素小于样本数列中的中间元素， 则在中间元素的左侧进行查找， 如果目标元素大于样本数列中的之间元素， 则在中间元素的右侧进行查找， 直到目标元素与可以比较的所有元素比较终了， 也没有找到相等的元素， 则表示查找失败， 可使用递归处理
int Binary_Search(int *sorted_array, int length, int key){ int low = 0, high = length-1, mid; while(low <= high) { mid = low + (high - low) / 2; if(key < sorted_array[mid]) { high = mid - 1; } else if(key > sorted_array[mid]) { low = mid + 1; } else { return mid; } } return -1; }
（2）算法评级
平均时间繁杂度 O(logN)， 请求样本元素有序
2.3 插值查找算法（ 二分法进级版）
（1）算法流程
基于二分查找算法，将查找点的选择改良为自适应选择，可以提高查找效力
int Insert_Search(int *sorted_array, int length, int key)
{
int low = 0, high = length-1, mid;
while(low <= high){
mid = low + (key - sorted_array[low]) / (sorted_array[high] - sorted_array[low]);
if(key < sorted_array[mid])
{
high = mid - 1;
}
else if(key > sorted_array[mid])
{
low = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
（2）算法评级
平均时间繁杂度 O(log(logN))， 请求样本元素有序
3. 经常使用的排序算法
3.1 冒泡排序算法
（1） 算法流程
a. 比较相邻位置的两个元素， 如果第一个元素的值比第二个元素大， 则交流位置
b. 对每一一对相邻的元素做相同的操作， 从开始的第一对到结尾的最后一对， 经由这一步， 最后的元素将是这组元素中的最大值
c. 对除了了最后一个元素之外的所有元素重复以上步骤
d. 延续对愈来愈少的元素重复以上步骤， 直到没有元素交流为止
void Bubble_Sort(int *array, int length){ int tmp = 0; for(int i=0; i<length-1; ++i) { for(int j=0; j<length-1-i; ++j) { if(array[j] > array[j+1]) { tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; } } } }
（2） 算法评价
平均时间繁杂度 O(N^2),不乱， 对样本的有序性无比敏感
3.2 插入排序办法
（1） 算法流程
a. 首先认为第一个元素有序，
b. 掏出一个元素， 让掏出的元素与已经有序的元素从后向前顺次进行比较
c. 如果左侧的元素大于掏出的元素， 则将左侧的元素值赋值到下一个元素的位置上
d. 如果左侧的元素小于等于掏出的元素， 则将掏出的元素赋值到左侧元素的右侧
e. 重复步骤 b， 直到处理终了所有元素为止
void Insert_Sort(int *array, int length){ int preIndex, current; for(int i=1; i<length; ++i) { preIndex = i -1; current = array[i]; while(preIndex >= 0 && array[preIndex] > current) { array[preIndex + 1] = array[preIndex]; preIndex--; } array[preIndex + 1] = current; } }
（2） 算法评价
平均时间繁杂度 O(N^2)， 不乱， 对样本的有序性无比敏感， 然而赋值的次数比冒泡排序少， 因而一般情况下略优于冒泡排序算法
3.3 选择排序法
（1） 算法流程
a. 从第一个元素起顺次掏出， 并且假设掏出的元素是最小值， 使用临时变量min 记录该元素的下标
b. 使用 min 记录的元素与后续的元素顺次进行比较
c. 如果后续元素中由比 min 记录的元素还小的元素， 则从新记录下标， 也就是后续元素变为了 min 记录的最小值
d. 直到 min 记录的最小值与后续所有元素比较终了， 交流 min 记录的元素与最开始假设的最小值
e. 重复上述步骤， 直到处理终了左右元素为止
void Select_Sort(int *array, int length){ int minIndex, tmp; for(int i=0; i<length-1; ++i) { minIndex = i; for(int j=i+1; j<length; ++j) { if(array[j] < array[minIndex]) minIndex = j; } tmp = array[i]; array[i] = array[minIndex]; array[minIndex] = tmp; } }
（2） 算法评估
平均时间繁杂度 O(N^2)， 不不乱， 对样本的有序不敏感， 尽管比较的次数比较多， 然而交流的次数比较少， 因而一般情况下也是略优于冒泡排序法
3.4 快速排序算法
（1） 算法流程
a. 选择中间元素作为基准值， 单独保留起来
b. 分别使用左右两边的元素顺次以及基准值进行比较， 将所有比基准值小的元素放在基准值的左侧， 将所有大于基准值的放在基准值的右侧， 等于基准值的元素可以放在任意一边， 这个进程叫做分组
c. 以递归的方式对小于基准值的分组以及大于基准值的分组分别进行再次分组，直到处理终了所有元素为止
void Quick_Sort(int *array, int left, int right){ if(left < right) { int i = left, j = right, tmp = array[left]; while(i < j) { while(i < j && array[j] >= tmp) //从右到左找到第一个小于tmp的数 j--; if(i < j) array[i++] = array[j]; while(i < j && array[i] <= tmp) //从左往右找到第一个大于tmp的数 i++; if(i < j) array[j--] = array[i]; } array[i] = tmp; Quick_Sort(array, left, i-1); Quick_Sort(array, i+1, right); }}
（ 2） 算法评价
平均时间繁杂度 O(NlogN),不不乱， 对样本的有序性不敏感
以上就是微观生活（93wg.com）关于“C语言基础知识(三)”的详细内容，希望对大家有所帮助！
评论