学习记录day18——数据结构 算法
算法的相关概念
程序 = 数据结构 + 算法
算法是程序设计的灵魂，结构式程序设计的肉体
算法：计算机解决问题的方法护额步骤
算法的特性
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[j+1] = arr[j]; //中的某个数，从那个数开始整体后移} //但实际上是逐个比较，逐个后移arr[j+1] = 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,mid+1,high); //对较大端进行递归return ;
}