自学考试 网页制作与网站建设06627,网站收缩引擎入口,合肥市城乡城乡建设局网站,网站建设总结报告书天行健#xff0c;君子以自强不息#xff1b;地势坤#xff0c;君子以厚德载物。 每个人都有惰性#xff0c;但不断学习是好好生活的根本#xff0c;共勉#xff01; 文章均为学习整理笔记#xff0c;分享记录为主#xff0c;如有错误请指正#xff0c;共同学习进步。… 天行健君子以自强不息地势坤君子以厚德载物。 每个人都有惰性但不断学习是好好生活的根本共勉 文章均为学习整理笔记分享记录为主如有错误请指正共同学习进步。 《送别》 寻阳五溪水沿洄直入巫山里。胜境由来人共传 君到南中自称美。送君别有八月秋飒飒芦花复益愁。 云帆望远不相见日暮长江空自流。 文章目录 数据结构和算法1. 时间复杂度和空间复杂度1.1 时间复杂度1.2 空间复杂度 2. 数组和链表的结构对比2.1 数组概念数组的特性 2.2 链表概念链表的特性常见的链表应用 3. 遍历一个树4. 冒泡排序 Bubble Sort4.1 算法描述4.2 复杂度4.3 代码实现 5. 快速排序 Quick Sort5.1 算法描述5.2 复杂度5.3 代码实现 6. 二分查找 Binary Search6.1 算法描述6.2 复杂度6.3 代码实现6.4 拓展 数据结构和算法
1. 时间复杂度和空间复杂度
时间复杂度和空间复杂度是衡量一个算法是否高效的重要标准 时间复杂度不是算法执行的时间这是错误的
1.1 时间复杂度
指的是算法语句执行的次数如O(1), O(n), O(logn), O(n2)
1.2 空间复杂度
指的是一个算法在运行过程中临时占用的存储空间大小即被创建次数最多的变量被创建了多少次这个算法的空间复杂度就是多少 如果算法语句中就有创建对象那么该算法的时间复杂度和空间复杂度一般一致 算法语句被执行了多少次就创建了多少个对象
2. 数组和链表的结构对比
2.1 数组
概念
相同数据类型的元素按一定顺序排列的集合 就是把有限个类型相同的变量用一个名字改名字就是数组名用编号区分数组中变量编号就是下标
数组的特性
数组必须先定义固定长度不能动态适应数据动态增减当数据增加时可能超出原先定义的元素个数当数据减少时造成内存浪费数据查询比较方便根据下标就可以直接找到元素时间复杂度O(1)增加和删除比较复杂需要移动操作数所在位置后的所有数据时间复杂度为O(N)
2.2 链表
概念
一种物理存储单元上非连续非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的
链表的特性
链表动态进行存储分配可适应数据动态增减插入、删除数据比较方便时间复杂度为O(1),查询必须从头开始找起时间复杂度为O(N)相当麻烦
常见的链表
单链表链表每一个元素都要保存一个指向下一个元素的指针双链表每个元素既要保存到下一个元素的指针还要保存一个上一个元素的指针循环链表在最后一个元素中下一个元素指针指向首元素
链表和数组都是在堆里分配内存
应用
快速访问数据较少或不插入和删除元素时用数组更好 较多插入和删除元素时使用链表数据结构更高效
3. 遍历一个树
四个遍历概念
先序遍历先访问根节点再访问左子树最后访问右子树后序遍历先左子树再右子树最后根节点中序遍历先左子树再根节点最后右子树层序遍历每一层从左到右访问每一个节点
每一个子树遍历时依然按照此时的遍历顺序可以采用递归实现遍历
4. 冒泡排序 Bubble Sort
4.1 算法描述
比较相邻的元素第一个比第二个大则交换两个元素位置对每一个相邻元素作同样的工作从开始第一对到结尾的最后一对在最后的元素应该会是最大的数对所有元素重复以上操作除了最后一个元素重复前面三个步骤直到排序完成
4.2 复杂度
排序方法时间复杂度平均时间复杂度最坏时间复杂度最好空间复杂度稳定性冒泡排序O(n2)2在n的右上角标O(n2)2在n的右上角标O(n)O(1)稳定
如果两个元素相等不会再交换位置所以冒泡排序是一种稳定排序算法
4.3 代码实现
冒泡排序
public class BubbleSort{public static void bubbleSort(int[] arr){for(int i 0; i arr.length-1; i){for(int j 0; j arr.length-i-1; j){if(arr[j] arr[j1]){//当前面的值大于后面的值交换位置int temp arr[j];arr[j] arr[j1];arr[j1] temp;}}}}public static void main(String[] args){int[] arr {4,2,5,1,9,3};bubbleSort(arr);for(int i : arr){System.out.print(i);}}
}5. 快速排序 Quick Sort
5.1 算法描述
使用分治法将一串list分为两个子串sub-list具体如下
从数列中挑出一个元素称为基准pivot重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任意一边。在这个分区退出后该基准数处于数列的中间位置这个称为分区操作partition递归地rcursive将小于基准值元素的子数列和大于基准值元素的子数列排序
5.2 复杂度
排序方法时间复杂度平均时间复杂度最坏时间复杂度最好空间复杂度稳定性快速排序O(nlog2n),2在log右下角标O(n2) 2在n的右上角标O(nlog2n) 2在log右下角标O(nlog2n) 2在log右下角标稳定
key值的选取可以有多种形式例如中间数或随机数分别会对算法的复杂度产生不同的影响
5.3 代码实现
快速排序
public class QuickSort{public static void quickSort(int[] data, int low, int high){int i,j,temp,t;if(lowhigh){return;}i low;j high;//temp为基准位temp data[low];System.out.println(基准位temp);while(ij){//先看右边依次往左递减while(tempdata[j]ij){j--;}//再看左边依次往右递增while(tempdata[i]ij){i;}//如果满足条件则交换if(ij){System.out.println(交换 data[i] 和 data[j]);t data[j];data[j] data[i];data[i] t;System.out.println(java.util.Arrays.toString(data))}}//最后将基准位与i和j相等位置的数字互换System.out.println(基准位 temp 和i、j相遇的位置 data[i]交换);data[low] data[i];data[i] temp;System.out.println(java.util.Arrays.toString(data));//递归调用左半数组quickSort(data, low, j-1);//递归调用右半数组quickSort(data, j1, high);}public static void main(String[] args){int[] data {3, 44, 34, 5, 25, 58, 20, 1, 57, 23, 12, 60, 43};System.out.println(排序之前\njava.util.Arrays.toString(data));quickSort(data, 0, data.length-1);System.out.println(排序之后\njava.util.Arrays.toString(data));}}6. 二分查找 Binary Search
6.1 算法描述
二分查找又称为折半查找是一种效率较高的查找方法要求列表中的元素是有序排列的即如果未排序则必须先排序才可进行二分查找假定表中元素按升序排序将表中中间位置记录的关键字与查找的关键字进行比较如果两者相等则查找成功如果不相等利用中间位置记录将表分成前后两个子表如果中间位置记录的关键字大于所要查找的关键字则进行查找前一个子表否则就去查后一个子表重复以上过程知道找到满足条件的记录使查找成功或直到子表不存在为止此时查找不成功
6.2 复杂度
二分查找法 时间复杂度为O(log2n) 空间复杂度为O(1)
6.3 代码实现
二分法查找
public class BinarySearch{public static int binarySearch(int[] arr, int left, int right, int findValue){if(leftright){//递归推出条件 找不到返回-1return -1}int midIndex (leftright)/2;if(finaValuearr[midIndex]){//向左递归查找return binarySearch(arr, left, midIndex, findValue);}else if(findValuearr[midIndex]){//向右递归查找return binarySearch(arr, midIndex, right, findValue);}else{return midIndex;}}public static void main(String[] args){//注意需要对已排序的数组进行二分查找int[] data {-40, -30, -12, -1, 2, 33, 38, 49, 50};int i binarySearch(data, 0, data.length, 33);System.out.println(i);}
}6.4 拓展
当有序数组中有多个相同的数值时如何将所有的数值都查到
代码
public class BinarySearch2{public static ListInteger binarySearch2(int[] arr, int left, int right, int findValue){ListInteger list new ArrayList();if(leftright){//递归退出条件找不到返回-1return list;}int midIndex (leftright)/2;int midValue arr[midIndex];if(findValuemidValue){//向左递归查找return binarySearch2(arr, left, mdiIndex-1, findValue);}else if(findValuemidValue){//向右递归查找return binarySearch2(arr, midIndex1, right, findValue);}else{System.out.println(midIndexmidIndex);//向左扫描int temp midIndex-1;while(true){if(temp0||arr[temp]!findValue){break;}if(arr[temp]findValue){list.add(temp);}temp - 1;}//将中间这个索引加入list.add(midIndex);//向右边扫描temp midIndex 1;while(true){if(temparr.length-1||arr[temp]!findValue){break;}if(arr[temp]findValue){list.add(temp);}temp 1;}return list;}}public static void main(String[] args){//注意 需要对已排序的数组进行二分查找int[] data {1, 4, 10, 58, 100, 1000, 1200, 1234, 1234, 3000, 4000};ListInteger list binarySearch2(data, 0, data.length, 1234);System.out.println(list);}
}感谢阅读祝君暴富
