4 排序与查找

课程内容#

排序#

四象限原则：稳定 / 非稳定、内部 / 外部
- 稳定：相同元素在排序前后的相对位置不变
- 内部：需要将数据整个加载到内存中进行排序

【考虑从小到大排序】

稳定排序#

插入（内部）
- 前：已排序区；后：待排序区
- 后面的数在前面找位置插空
  - 一个一个比较、交换，实现【插入】的效果
  - 不是直接和插入位置交换，这样会打乱已排序区的顺序
- 平均时间复杂度：O (N^2)
冒泡（内部）
- 前：待排序区；后：已排序区
- 从第一个元素向后驶进，找到一个最大元素放在已排序区最前、待排序区最后
- 进行 N - 1 轮冒泡，每轮在已排序中增加一个元素
  - 【优化】当某一轮冒泡过程没有进行交换操作，可以直接结束
- 平均时间复杂度：O (N^2)
  - 最优时间复杂度：O (N)←已排序
  - 最坏时间复杂度：O (N^2)←完全逆序
- 插入排序可理解为反向冒泡
归并（外部）
- 前言：两个有序的数组（长度分别为 m、n）合并成一个有序的数组
  - 时间复杂度：O (m + n)
- 先分治到两两可以比较大小，再把有序的数组两两合并
- 时间复杂度（最优、最坏、平均都是）：O (NlogN)
  - 共 logN 层，每层的合并时间为 O (N)
- 【外部排序】2 路归并 (上述)、k 路归并 (多路归并，利用堆)
  - 参考外归并排序- 维基百科，每路的排序方法可以任意，最终归并
  - 其实这个外部排序与否取决于你想不想、需不需要，但它可以

不稳定排序#

选择（内部）
- 前：已排序区；后：待排序区
- 每轮从待排序区中选择一个最小的元素与待排序区的第一个元素交换
  - 可能会有自身与自身交换的情况，所以交换函数不能用异或了
- 不稳定：例如 22'1，在第一次交换后，2 就跑到了 2' 的后面，即 12'2
- 时间复杂度（最优、最坏、平均都是）：O (N^2)
- 一般情况下优于冒泡，两者比较次数差不多，但冒泡的交换太频繁
快排（内部）
- 【基准值、partition】
  - 拿出第 1 个元素作为基准值
  - 【尾指针】先从后往前找小于基准值的元素，放到第 1 个元素位置 (已为空)，【头指针】再从前往后找大于基准值的值，放到刚刚空出的位置，循环
  - 最后头尾指针重合，指向一个空位置，放入基准值
  - 再对基准值左右两部分分别进行以上操作
- 时间复杂度：O (NlogN)
  - 逆序数列选第一个元素为基准值时，退化为选择排序，O (N^2)
- 【优化】
  - 基准值随机选
  - 减少递归的使用，用循环做
  - 左右都找到一个要交换的值后，再交换

查找#

朴素二分
- 前提：单调序列
- 如果要查找的值在序列中重复存在，二分查找分辨不出找到的是哪一个
特殊二分
- 11110000
  - 引入虚拟头指针，索引为 - 1
  - mid 计算需要 + 1，避免死循环，比如 10 情况
- 00001111
  - 引入虚拟尾指针，索引为 n [数组范围为 0 ~ n - 1]
- 参考《面试笔试算法上》——2. 二分专题
- 这里比参考内容还增加一个虚拟指针的概念，通过更改查找的边界 [-1 ~ n -1 或 0 ~ n]，可以反映找不到值时的情况
三分查找
- 解决【求凹凸函数极值点】问题
- 将原问题的规模分成三分之一
- 更新策略：保留值小的元素与另一端的区间；停止条件：|m1 - m2|< ESPL
- 时间复杂度：O (log [3] N)，比二分查找 O (log [2] N) 稍慢

哈希表#

用于查找的【数据结构】
结构定义
- 需要一片连续的空间，存储元素
- 与顺序表一致，元素类型可变
结构操作
- 哈希函数：可以把任意类型元素映射成整型值 [数组下标]
  - 然后可以存储某值到对应的数组下标中
  - 数组下标只能是整型
- 冲突处理方法
  - 开放定值【常用】：往后看看有没有空位，如二次探测法... 但容易产生数据堆聚问题
  - 再哈希：又名散列法，使用多种哈希函数
  - 拉链法【常用】：用链表结构存储每个位置的元素
  - 建立公共溢出区：把冲突的元素统一放到一个特定区域
查找的时间复杂度：趋近于 O (1)
- 其他耗时：哈希函数转换、拉链法 [查找链表元素] 或其他冲突处理方法导致的耗时
- 只有数组、顺序表是 O (1) 的
哈希表的空间利用率一般是 50~90%
- 哈希函数一定会存在冲突情况，开辟空间时需要预留
- 当利用率可以达到 70% 时，它就可以在工业上使用了，冲突越少，利用率越高，哈希函数越优秀

代码演示#

稳定排序#

详见注释和红框标记
要保证稳定排序的稳定性，注意 == 的情况，不能交换 [或保证原有的顺序]！
【注意】调用 TEST 宏时，后一个数组是 num，它是在宏定义里拷贝 arr 得到的一个数组！

不稳定排序#

V1.0 版：选择排序 & 快速排序普通版#

重点关注快排算法，有很多可优化点
- 【自行优化】46、48 行的 num []> z 或 num [] < z 可以加上 == 条件，这样在遇到相等的元素不会交换，也没必要交换，还能尽量保证算法稳定 [虽然快排不稳定]
- 【待优化点】基准值选择、递归→循环、交换方式

V2.0 版：快速排序优化版#

实现上述所提到的 3 个待优化点
注意几个边界的 ==：x <= y、num [] < z、num [] > z
- ❓== 的判断怎么理解？详见下面思考点 2
第 39、40 行：排序右区间，排好后缩小右边界

2 个版本快速排序的速度比较#

分别测试随机序列和逆序序列
- 20 万大小的随机序列：两者差距甚微
- 10 万大小的逆序序列：差别明显
  - 对于 20 万的逆序序列，原始版快排会爆栈

二分查找#

虚拟指针的使用，可以避免没有答案时 [000000] 返回假答案 [0 或 n - 1] 的情况
11110000 的情况，在计算 mid 时要 + 1，避免陷入死循环，如 10
详细可见《面试笔试算法上》——2. 二分专题

建立字符串的哈希表#

哈希函数：BKDR-Hash，冲突处理方法：拉链法
插入值时使用的是头插法
哈希表结构的利用率不可能达到 100%，所以开辟的空间需要扩大，一倍
calloc 开辟哈希表空间，可以让每个位置的链表首地址置空，安全
哈希函数可以自己设计

思考点#

【自己的理解】要保证稳定排序的稳定性，注意 == 的情况，不能交换 [或保证原有的顺序]！
❓关于快速排序优化版中边界的思考
- 同样按照普通版快排优化边界判断，下面优化的思路有问题，而在普通版均可实现
  - 32 - 33 行：num [] < z 和 num [] > z 分别改称 <= 和 >=，会出现【段错误或死循环】
    - 对于 num [] <= z 【死循环】
      - 举例：2 1 ，基准值为 2，左指针 x 一直走到右端，出界，而右指针 y 不变，第 27 行 while (l < r) 成立，x 又回到 l，变成了死循环
    - 对于 num []>= z 【段错误 —— 爆栈】
      - 举例：1 2，基准值为 1，右指针 y 一直走到左端，变 - 1，而左指针 x 和 r 不变，第 39 行 quick_sort (num, x, r) 不断递归调用，最终爆栈
    - 分析原因：普通版把基准值拿出来了，优化版基准值还在里面，需要考虑这个区别
  - 32 - 34 行：x <= y 改成 x < y，也会出现【段错误】
    - 举例：2 3，基准值为 2，此时 x、y 分别指向 2、3，经过循环，x、y 都指向 2，而 x 和 r 都不变，第 39 行 quick_sort (num, x, r) 不断递归调用，最终爆栈
    - 分析原因：x、y 要错开，不然有点像特殊二分 111000 不 + 1 的情况
  - 小结：x、y 都得动起来，x 不动导致爆栈，y 不动导致死循环
  - 【个人理解，考虑不周，欢迎探讨】
三分查找 —— 练习题
- 先确定边界：INT32_MIN ~ INT32_MAX
- 后面按三分查找的步骤来即可
- 边界思考
  - 根据公式 - b / 2a 估计，但有些作弊嫌疑
  - 根据二次函数 = 0 的两个解确定范围，但弄复杂了
  - 三分查找效率是 logN 级别，边界范围大小影响不大

Tips#

十大经典排序算法 (动图演示)-cnblogs
十大经典排序算法动画与解析，看我就够了- 五分钟学算法

课程速记#

提前预习堆与优先队列，还有并查集的内容