西安市建设干部学校网站,厦门网站优化服务,创建全国文明城市工作总结,合肥百度快照优化排名前言程序数据结构算法#xff0c;好的算法能让程序更高效的运行#xff1b;在当今数据信息时代#xff0c;数据分析和数据处理肯定是避免不了#xff0c;而算法便成为了很多公司门槛级的要求#xff0c;特别是大厂#xff1b;赶紧搞起来#xff0c;说不定离进大厂就只差… 前言程序数据结构算法好的算法能让程序更高效的运行在当今数据信息时代数据分析和数据处理肯定是避免不了而算法便成为了很多公司门槛级的要求特别是大厂赶紧搞起来说不定离进大厂就只差一步呢(算法)~~~算法简介算法是一组完成任务的指令任何代码片段都可视为算法。如下image-202103241757217951. 算法五大特性有穷性一个算法必须在执行有限步之后结束且每一步都可在有限时间内完成。通俗一点理解就是不能出现类似死循环这样导致算法无法结束。确定性算法中每条指令必须有确切的含义对于相同的输入只能得出相同的输出。可行性算法中描述的每一步操作都可以通过已经实现的基本运算执行有限次来实现。输入一个算法有零个或多个输入。就好比一个方法可以不传递参数也可以传递参数。零个输入时其实代表算法本身设有初始条件。输出一个算法有一个或多个输出这些输出是与输入有着对应关系的量。没有输出的算法是毫无意义的。一个好的算法还应该有如下特征正确性能正确解决问题结果正确可读性算法实现步骤容易读懂健壮性算法能处理异常情况比如输入不合法时算法能给出对应处理高效率、低存储时间复杂度低空间复杂度低即运行快占用内存少。2. 衡量算法好坏的标准度量一个算法好坏可以从两个维度进行判断时间复杂度事先预估执行完算法的时间开销数量级由于数据量多少、硬件配置、程序语言等因素会直接影响到算法的执行时间比如同样的算法数据量少的肯定快硬件配置高的肯定快所以不能用算法执行完成后的具体时间来衡量一个算法的好坏。一个算法可以预估其时间开销级别(不受外界其他条件影响)通常使用大O表示法来表示来个例子image-20210325084348799上图方法为了方便理解假设每一步需要1ms当传入的n1000时每一步耗时如下①只执行一次所以消耗1ms②由于每次循环需要判断需要则需要1001次消耗1001ms③和④在循环体中所以分别需要执行1000次总共消耗2000ms所以总耗时为T(1000)110012*1000具体时间和传入的n有关系则总耗时为T(n)1(n1)2n这里T代表时间通常说时间复杂度的时候都不带单位。为了更加简洁直观会使用大O表示法去掉常数部分和系数部分如下T(n)1(n1)2nO(n)因为当n足够大时系数和常数对算法度量的影响不大这里就不细说啦空间复杂度事先预估执行完算法的内存开销数量级 空间复杂度和时间复杂度类似同样可以用大O表示只是这个表示的是算法所消耗的内存比如int占用4个字节上图中用到中间变量nResult在不考虑其他容量的情况下消耗了4个字节用大O表示法依然是去掉常数和系数对于常量的的表示为O(1)对于时间复杂度和空间复杂度对应的数量级别越小算法越高效。常遇到到级别从好到差的顺序如下3. 算法的稳定性若待排序数据中有两个相等的元素A和B在排序前A在B前面如果使用某种排序算法后A仍在B前面则称这种排序算法稳定否则就不稳定。但稳定性不能用来衡量一个算法的好坏只能算是算法的一个性质对于一些场景根本就不在乎两个相等元素的顺序。从排序开始排序在实际开发中用的比较多就先从这入手吧排序分为内部排序和外部排序两种内部排序在排序期间元素全部存在内存中进行排序常见的插入排序、交换排序、选择排序都是内部排序。外部排序在排序期间元素无法全部存放在内存中必须在排序过程中不断地在内、外存之间移动。1. 先来说说直接插入排序1.1 算法思想插入排序就是每次将一个待排序的数据插入到一个前面已排好序的子序列中初始认为第一个元素就是排好序的序列依次比较然后插入到合适位置直到完成排序为止。插入排序的关键如下将待排序数据分为三部分已经排好序的数据、下一个需要插入的数据、待排序的数据每一次都从待排序数据中取出一个需要插入的数据将其放在哨兵位置将哨兵位置的数据(其实就是要插入的数据)与已排好序的数据进行比较如果符合条件就插入到对应位置其他数据统一向后移位即可1.2 算法实现与解析算法代码如下(升序)image-20210325135045509执行结果如下image-20210325134622616解析排序步骤过程如下image-20210325214501972步骤说明图中绿线框部分代表是已经排好序的列表箭头指的元素是下一个要插入的元素黄线框部分为剩下的无序元素。黄方块为每次移动的数据绿方块表示最后有序列表腾出的位置。将原始数据array复制到新数组中arrayb中这步的主要目的是后续不需要声明额外临时变量也为了后续核心代码实现逻辑简单易懂减少过多的判断第1步将第一个元素作为有序列表(第一元素为2)下一个要插入的元素为5将5放入哨兵位置即索引为0的位置然后依次遍历有序列表中的元素与哨兵位的值5比较这里只有2和5比较2小于5所以不需要改变位置第2步有序列表中的元素有2和5,下一个要插入的元素为6将6放入哨兵位置即索引为0的位置然后依次遍历有序列表中的元素(2和5)与哨兵位的值6比较都小于6所以不需要改变位置第3步有序列表中的元素有2、5、6,下一个要插入的元素为1将1放入哨兵位置即索引为0的位置然后依次遍历有序列表中的元素(2、5、6)与哨兵位的值1比较第3-1步由于是倒序遍历先用有序列表中的6与1进行比较6大于1所以6往后移一位第3-2步继续遍历用有序列表中的5与1进行比较5大于1所以5往后移一位第3-3步继续遍历用有序列表中的2与1进行比较2大于1所以2往后移一位第3-4步遍历完有序列表中的元素要插入的元素和哨兵位的元素相等终止遍历然后将哨兵位的元素(当前哨兵位为1)赋值给腾出的空间(腾出的索引位为1)第4步有序列表中的元素有1、2、5、6,下一个要插入的元素为9将9放入哨兵位置即索引为0的位置然后依次遍历有序列表中的元素(1、2、5、6)都小于哨兵位的值9所以不用插入位置不变第5步有序列表中的元素有1、2、5、6、9,下一个要插入的元素为3将3放入哨兵位置即索引为0的位置然后依次遍历有序列表中的元素(1、2、5、6、9)与哨兵位的值3比较第5-1步由于是倒序遍历先用有序列表中的9与3进行比较9大于3所以9往后移一位第5-2步继续遍历用有序列表中的6与3进行比较6大于3所以6往后移一位第5-3步继续遍历用有序列表中的5与3进行比较5大于3所以5往后移一位第5-4步继续遍历用有序列表中的2与3进行比较2小于3终止遍历然后将哨兵位的元素(当前哨兵位为3)赋值给腾出的空间(腾出的索引位为3)第5步完成之后已完成黄线框中无序元素的排序排序也就完成啦最终的结果就是1、2 、3 、5 、6 、9。这样对比着图看详细说明是不是好理解了很多。如果有小伙伴不太理解上面的代码可以使用定义临时变量作为哨兵的方式步骤和上面基本一样只是哨兵不一样如下image-202103252356484021.3 算法分析主要从时间复杂度、空间复杂度、是否稳定来进行分析时间复杂度分析时间复杂度时会从最好、平均、最坏三种情况进行分析最好时间复杂度传入的数据是有序的(和最终的结果一致)所以每次遍历一次就能找到位置所以插入排序的最好时间复杂度为O(n)和传入的元素个数有关最坏时间复杂度传入的数据完全和要的结果相反所以每次都需要进行两次循环进行找到合适位置插入所以最坏时间复杂度为O(n2)平均时间复杂度也就是O(n2)空间复杂度在算法核心部分只采用了固定的几个中间变量(i,j,arrayb[0])所以算法过程中消耗的内存是一个常量则空间复杂度为O(1)稳定性由于在算法过程中采用的是小于符号进行比较遇见相等的数据时就终止判断所以不会影响原有的数据顺序则直接插入排序是稳定的。综上所述插入排序的时间复杂度为O(n2)空间复杂度为O(1)是稳定算法总结第一篇复习了一下关于算法相关知识然后以简单的直接插入排序收尾后面会依次总结其他算法还是图解加说明的方式让每一个算法学起来更简单。
