基础算法学习

使用 typescript 实现常见的算法和数据结构

排序

1. 基础排序

   • 选择排序
   • 插入排序
   • 冒泡排序（作业）
     • 待优化
   • 希尔排序（作业）

2. 进阶排序

   • 归并排序
   • 快速排序
   • 归并排序和归并排序都使用了分治算法
     • 逆序对，衡量数组的有序程度
     • 取数组中的第 n 大的元素, 简化后取数组中的最大值，最小值
   • 堆排序

3. 排序小结

   • 插入排序, O(n^2), 原地排序，使用额外空间 O(1), 稳定排序
   • 归并排序， O(nlogn), 非原地排序， 使用额外空间 O(n)， 稳定排序
   • 快速排序， O(nlogn), 原地排序， 使用额外空间 O(nlogn)，不稳定排序
   • 堆排序， O(nlogn), 原地排序， 使用额外空间 O(1), 不稳定排序

数据结构

1. 堆
   • 使用堆实现优先队列
   • 在 N 个元素选出前 M 个元素， 如一百万个元素中选出前 100 名， NlogM
   • 多路归并排序
   • 二叉堆，左右两个孩子
   • d 叉堆，可以有多个孩子
   • 最大堆，最小堆，最大索引堆，最小索引堆
   • 堆的优化
     • shiftUp 和 shiftDown 中的赋值操作替换 swap 操作
     • 表示堆的数组从 0 开始
     • 没有 capacity 的限制，动态调整堆中数组的大小
   • 最大最小队列

查找

1. 二分查找

   • floor, 元素在数组中第一次出现的位置，找不到返回 floor 之前的元素位置
   • ceil, 元素在数组中最后一次出现的位置，找不到返回 ceil 之后的位置