如何网站做百度推广,网络架构师报考条件,微信主题wordpress,手机网站开发注意的问题算法的相关概念 程序 数据结构 算法
算法是程序设计的灵魂#xff0c;结构式程序设计的肉体
算法#xff1a;计算机解决问题的方法护额步骤
算法的特性
1、确定性#xff1a;算法中每一条语句都有确定的含义#xff0c;不能模棱两可
2、有穷性#xff1a;程序执行一…算法的相关概念 程序 数据结构 算法
算法是程序设计的灵魂结构式程序设计的肉体
算法计算机解决问题的方法护额步骤
算法的特性
1、确定性算法中每一条语句都有确定的含义不能模棱两可
2、有穷性程序执行一段时间后会自动结束
3、输入有零个或多个输入
4、输出至少一个输出可输出多个
5、可行性经济可行性、社会可行性、能够运行 算法的设计要求
1、正确性给定合理的输入数据能够得到正确的结果
2、健壮性对于给定的不合理的输入数据能够给出相应的处理措施
3、可读性程序核心代码写注释、程序代码有缩进、程序代码命名规范
4、高效率要求设计复杂度尽可能低
5、低存储要求空间复杂度尽可能低 时间复杂度
算法执行消耗时间的度量
计算公式T(n) O(f(n)); T(n):时间复杂度 n:表示问题的规模 f(n):是问题规模与执行次数之间的函数 O(f(n)):使用O阶记法记录算法时间复杂度 常见的数据复杂度 排序算法 根据数据元素的关键字按照升序或降序的方式将数据元素重新排列的过程称为排序
排序的分类
1、交换类冒泡排序、快速排序
2、选择类简单选择排序、堆排序
3、插入类直接插入排序、折半插入排序
4、归并类二路归并、多路归并 冒泡排序
1、在排序过程中越大(小)的数据经由交换后会慢慢的“浮”到顶端如同气泡一样 2、冒泡排序原理 1比较相邻元素如果第一个比第二个大小则交换 2经过一趟排序后会使最大最小的元素落到最后 重复上面的步骤直到没有任何一对 数字需要比较为止 3当某一趟的排序过程中出现没有数据交换的过程则结束整个排序
3、算法 void bubble_sort(int *arr, int n)
{for (int i 1; i n; i) //外循环 控制趟数 {int flag 0; //定义一个标志位 及 标准位重置for (int j 0; j n - i; j) //内循环 交换位置{if (arr[j] arr[j 1]) //判定是否交换升序排列{flag 1; //标志位 置1int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}if (flag 0) //标志位为0 说明未进入if语句 即排列已完成 直接退出循环{break;}}printf(bubble_sort on\n);
}选择排序 每次从待排序序列中找到最大(小)值将其与待排序序列的第一个进行交换 1、排序步骤 1从待排序序列中选择最值 2如果最值不是待排序序列的第一个则进行交换 3从剩余待排序序列中继续重复前两次的操作直到待排序序列为空
2、算法
void select_sort(int *arr, int n)
{int min 0; //定义一个变量 存储最小值for (int i 0; i n; i){min i; //记录下标for (int j i 1; j n; j){if (arr[min] arr[j]) //更新最小值{min j;}}if (min ! i) //如果最小值不是待排序序列第一个 则换置换{int temp arr[min];arr[min] arr[i];arr[i] temp;}}printf(select_sort on\n);
}直接插入排序
每次从待排序序列中选择第一个将其插入到已排序序列中 1、排序步骤 1选取待排序序列中的第一个元素 2跟前面的元素依次比较如果前面的比当前元素大小则将前面的元素后移一位 3直到出现前面的不比当前的大小或者已经到最前面了将选取的元素放入空位置上 4对于待排序序列中的所有元素重复上述操作
2、算法 void insert_sort(int *arr),int n
{int i,j; //需要在循环外使用for (i 1; i n; i){int temp arr[i]; //记录要移动的元素数值 for ( j i-1; temp arr[j] j 0; j--) //实现的效果 { //如果记录的数值小于等于已排列序列arr[j1] arr[j]; //中的某个数从那个数开始整体后移} //但实际上是逐个比较逐个后移arr[j1] temp; //后移结束 插入记录的元素数值 }printf(insert_sort on\n);
}
快速排序 快速排序是在序列元素与选定基准元素比较分割为大小两部分的交换排序 时间复杂度O(nlog2n) n倍以2为底2的对数 1、排序步骤 1从待排序列中任取一个基准元素 2与基准元素比较将待排序列分割为大小两部分 3再对各部分重新选择基准元素并依此规则排序 直到每个部分只剩一个元素为止 2、算法
int part(int *arr,int low ,int high)
{int X arr[0]; //将第一个元素定为基准while(low high) //循环条件{while (low high arr[low] X) //避免错位 {high--;}arr[low] arr[high]; //将小值前置while (low high arr[high] X){low;}arr[high] arr[low]; //将大值后置}//循环结束 此时 low higharr[low] X; //将基准放入指定位置return low; //返回基准下标
}
void quick_sort(int *arr ,int low ,int high)
{if (low high) {return; //递归出口 只有一个元素时}int mid part(arr,low,high); //找到基准quick_sort(arr,low,mid-1); //对较小端进行递归quick_sort(arr,mid1,high); //对较大端进行递归return ;
}
