7_2数据结构与算法基础：：：算法

源地址

7.22 算法的特性

确定性：不管输入多少次1结果只能是1，而不能出现其他数字
有穷性和有效性比较：

• 有穷性：步骤的数量
• 有效性：每一个步骤都能得到有效的结果

7.23 算法的时间复杂度和空间复杂度

算法的时间复杂度和空间复杂度的概述

对树的处理时，经常会用到：o(log2n)

• n表示结点，算出来的就是层数

7.24 顺序查找与二分查找

顺序查找

时间复杂度：O(n)

二分查找

时间复杂度：O(log2n)
前提：要有序


细节：

• 除的是下标，且小数时向下取整。
• 中级值比较后，就不需要比较了比如12中间值是6，则从1-5进行比较。

例题讲解【2017年上】

1. （1+12）/2 = 6.5，向下取整为6，9在6的右侧，则算右区间时候6+1
2. （7+12）/2 = 9.5，向下取整为9，得到结果

7.25 散列表【Hash table，也叫哈希表】

在存储的时候就想要一定的规则（如上面的散列函数），存到相应的空间里。

冲突的解决方法

线性探测法：在同一个位置冲突的时候，可以放到下一个单元
伪随机数法：
还可以再散列的方式：

注：理论上散列表效率高，但是有冲突之后，解决冲突后又会降低效率（所以要做前期设计降低冲突效率）

例题讲解【2021上】

7.26 排序【重点知识点】

1.排序的概念

稳定与不稳定排序

• 稳定：一组数中有两个键值一样的数，他们的顺序不会因为排序之后发生改变。

内排序与外排序

• 内：指的是在内存中进行的排序
• 外：会涉及到外部存储空间

例题讲解【2021上】

7.27 插入类排序：直接插入排序

• 插入一个数前，这组数已经排好序了，插入时从后面大数开始向前比较。
• 速度慢

7.28 插入类排序：希尔排序

基本步骤：

1. 首先取一个小于n的d1做为增量（d1=n / 2），本题为5，然后就每隔5位数就组成一对
2. 随后将每一小组按照直接插入排序进行排序
3. 然后，取第二个增量为（d2 = d1 / 2）【除数取基数】，本题为3，然后就每隔3位数就组成一对
4. 随后将每一小组按照直接插入排序进行排序
5. 以此类推，直到增量dt=1为止。

效率问题：当问题空间比较大的时候，效率比直接插入排序高（因为最后一次比较基本有序了，不需要从大到小依次排序）

7.29 选择类排序：直接选择排序

7.30 选择类排序：堆排序

堆基本特性的简单解释：

• 所有的孩子结点都小于根结点，这样的情况属于大顶堆
• 所有的孩子结点都大于根结点，这样的情况属于小顶堆

例题讲解【2021下】

例题讲解【2017年上】

堆的基本操作：

1. 堆结构建立起来根结点就是最大/小值
2. 将根结点取出排到第一个
3. 再将剩下的进行堆排序，排序之后在取出根结点排到第二个
4. 依此类推把堆里元素全部取走
   

重要的步骤——初建堆【大顶堆为例】：

• 按完全二叉树的方式来建堆
• 局部的小调整
  • 从最后一个非叶子结点开始调，这里是5
  • 查看5是否大于它的两个孩子，如果小于其中一个孩子结点，则和孩子结点中的最大值进行交换
    
• 接下来调倒数第二个非叶子结点，这里是4
• 接下来轮到了3这个结点
  • 这里需要多级调节，因为换位之后3比5小，所以还需要再下面的小树中进行调整
    
• 以此类推：
  

重要的步骤——取走后的堆的重建过程【大顶堆为例】：

• 取走后将最后一个结点补充到根结点位置
• 接下来步骤和初建堆步骤一样
• 以此类推下去就能得到一个完整的排序列表
  
  总结：
• 由于用到了类似树的特殊结构，所以效率要比直接选择排序高
• 应用场合：数特别多的时候求前10名次的场景

例题讲解【2021上】

大顶堆

7.31 交换类排序：冒泡排序

• 冒泡基本思路
  
• 特别注意的地方：下标的变化范围

C语言排序算法-冒泡排序

• 注：%d是输出整数，中间的-4是指输出占用4个字符宽度，如果实际输出不足4位则右补空格，否则按实际宽度输出，如果去掉负号写成%4d,就是左补空格，其余含意一致。

Java基础(冒泡排序)

7.32 交换类排序：快速排序

基本步骤：

1. 先定一个基准（左）
2. 如果用基准（左）和列表指针（右）进行比较，如果基准大就进行交换，否则指针（右）继续向左移动
3. 如果用基准（右）和列表指针（左）进行比较，如果基准小就进行交换，否则指针（左）继续向右移动
4. 大于基准的都放到了右边，小于的都放到了左边
5. 经过一轮之后，基准跑到了中间。
6. 再采用相同的方式对左右两组进行排序，直到所有记录都排序到了相应的位置

注：递归的解决每个小问题
注：该方法是高效的

7.33 归并排序【了解】

基本步骤：

1. 先两两配对
2. 前两组做归并，后两组做归并
3. 归并排序流程：
   • 将两组第一位进行比较，将小的值放到R数组的第k个单元
   • k+1就是R数组下一个位置
   • i+1，j+1就是组中下一个位置

算法核心理念：将一个大问题拆成各种小问题

• 也就是分治算法：“分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。”

例题讲解【2021下】

考察：归并排序将问题先分解、再处理、再合并的方式采用了分治法的思想

7.34 基数排序【了解】

7.35 排序算法的时间复杂度和空间复杂度（辅助存储）及稳定性【记忆】

• 注：设计到树结构的一般时间复杂度都包含：O(nlong2n)
• 占用辅助存储空间最多的室归并排序

例题讲解【2021下】

考察：归并排序是稳定排序，没有所谓的最好和最坏排序算法，都为O(nlgn)

例题讲解【2022下】61

例题讲解【2021上】