章节大纲查找排序一、查找顺序折半哈希1、顺序查找定义最基础的查找方式从头到尾一个一个比对。核心原理暴力遍历。不管数据有没有顺序挨个问“你是那个数吗”时间复杂度O ( n ) 最坏情况要找遍所有人;O ( 0) (最好情况1次找到)优点算法简单对数据没有任何要求有序无序皆可适合链表(逻辑连续物理不一定连续)。缺点效率低数据量大时非常慢。应用场景数据量较少或者数据完全无序且只查一次的情况。2、折半查找二分查找定义也叫折半查找在有序序列中每次都拿中间的数来比对排除掉一半的可能性。核心原理分治法。比中间小去左边找。(有序递增)比中间大去右边找。(有序递增)优点查找效率非常高。缺点前提必须是有序数组。如果为了查找而去专门做一次排序成本可能划不来不适合频繁插入删除的数据维护有序性成本高。应用场景静态的、已排序的大量数据如字典查字、图书馆索书号3、分块查找索引顺序查找4、哈希表定义通过一个数学公式哈希函数直接算出数据应该存放的地址。核心原理地址映射。地址 f(关键字)。时间复杂度理想情况下为 O ( 1 )一次命中。优点查找速度最快几乎不需要比较。缺点需要额外的存储空间空间换时间可能会产生“冲突”数据是无序的。应用场景需要极速查找的系统如缓存系统Redis、数据库索引、身份证查询常见的冲突解决方法1、开放定址法key/mod取余数哈希地址类似数组的下标有冲突的直接从当前位置向后移动找到第一个空的位置保存2、链地址法有冲突的情况下直接用直接指向重复的key即可二、排序定义2、1 第一梯队简单排序直接插入冒泡简单1、直接插入排序(稳定)有序增序或降序核心当数据基本有序时它是最快的排序方法2、冒泡排序稳定两两比较大的往后移。每一轮循环最大的那个数就像气泡一样浮到了最后面3、简单排序不稳定2、2 第二梯队高级排序1、快速排序不稳定核心原理分治法 基准兵。1、随便找个“基准数”Pivot比如第一个数。2、把比它小的都扔左边比它大的都扔右边。3、然后对左边和右边分别再做同样的事递归。优缺点优点平均速度最快。缺点不稳定。最坏情况数据本身倒序会退化成冒泡排序 O ( n 2 )考点它是所有同数量级排序中平均性能最好的。但它对内存栈有消耗递归2、堆排序:不稳定核心原理利用完全二叉树。1、把数据构建成一个大顶堆根节点最大。2、把堆顶最大值和末尾元素交换排除末尾剩下的重新建堆。优缺点优点空间复杂度 O ( 1 ) O(1)O(1)不需要额外内存。缺点不稳定3、归并排序:稳定定义两两合并左小右大优缺点优点稳定这是它比快排和堆排强的点。效率非常稳定永远是 O(nlogn)缺点费空间。需要一个和原数组一样大的辅助空间O ( n )考点空间换时间的典型代表4、基数排序稳定定义按照 个位 、十位、百位依次排序最终得到最终答案查找和排序总结数据结构与数据运算总结数据结构 数据怎么存数据运算 数据怎么处理二者是数据结构课程两大核心一、数据结构基本概念数据所有能被计算机处理的符号集合数字、字符、图像等数据元素数据的基本单位一个记录、一条对象数据项数据不可分割的最小单位元素里面的字段数据结构相互之间存在一种或多种特定关系的数据元素的集合。包含三方面逻辑结构、存储结构、数据运算。逻辑结构数据之间抽象的关系和计算机无关线性结构一对一代表线性表、栈、队列、串特点除首尾每个元素只有一个前驱、一个后继非线性结构一对多 / 多对多树一对多二叉树、森林图多对多有向图、无向图集合元素只有 “同属一个集合”无其他关系存储结构物理结构内存中怎么存放逻辑结构是思想物理结构具体计算实现。顺序存储连续内存数组实现随机访问插入删除慢。链式存储不连续结点 指针只能顺序访问插入删除快。索引存储数据 索引表通过索引快速定位。散列哈希存储通过哈希函数直接计算存储地址。二、数据运算对数据结构可以做的操作—时间和空间的博弈数据运算是定义在逻辑结构上实现在存储结构上。1、常见基础运算查找在结构中找指定元素插入把新元素加入结构删除移除指定元素修改更新某个元素的值排序将元素按关键字重新排列遍历依次访问每一个元素线性遍历、树遍历、图遍历2、时间复杂度 空间复杂度衡量运算好坏时间运算的时间长短空间占用存储空间的多少思考题为业务选择合适的数据结构答题模板分析业务需要的数据运算主要做什么频繁插入频繁查找随机读取选择逻辑结构线性 / 树 / 图选择存储结构顺序 / 链式说明该结构对于插入、查找操作时间复杂度说明为什么适合该场景。例子频繁增删不经常随机读取 →选链表频繁随机读取、很少增删→选顺序存储数组