一、排序算法

选择性排序：

对[0.....n-1] 长度为n的数组排序

1. 选择排序

• 从0开始遍历数组：
  • 后面位置依次与当前位置比较
    • 小于当前位置的交换
• 遍历结束，排序结束

O(n²)

O(1)

不稳定

2. 冒泡排序

• 每次遍历确定最后一位置的数据顺序
  • 遍历过程相邻两个比较
    • 大的后移

O(n²)

O(1)

稳定

3. 插入排序

• 每次遍历保证0到当前位置有序
  • 新位置与有序位置的最后位置比较
    • 小的交换

O(n²)

O(1)

稳定

4. 归并排序

• 递归处理
  • 每次二分，合并左右两部分
    • 依次比较左右
      • 小的等于的先放入辅助数组，然后++
      • 一边遍历完后，另一边直接复制

O(nlogn)

O(n)

稳定

5. 快速排序

• 随机选择一个数作为参照，将其与最后一个交换
  • 小于参照的放左边，等于参照在中间，大于参照放右边
  • 得到小于区，等于区，大于区，拿等于区边界[l,r]来标识
    • 等于区域的数据已经排好序
    • 小于、大于部分做递归处理，主要进行分区操作：
      • 与标准比较：
        • 小于： 与小区区域下一个数据交换，小于区右扩一
        • 等于：不动，当前位置右移一
        • 大于：与大于区域前一个数据交换，大于区左扩一
      • 最后，最后一个参考数与大于区的第一个数交换，大于区左边界右移一

O(nlogn)

O(logn)

不稳定

6. 堆排序

堆的两种操作：

• 插入： 向堆中插入一个数据，当前数据与其父节点比较调整，保持最大堆推结构。向上调整 O(logn)
• 堆化：随便一个堆，通过对当前节点与其子节点的比较调整，保持子树的最大堆结构。向下调整 O(logn)

• 数组放入大根堆

• 依次取出根节点，从后往前排序，取出后调整堆，使其保持最大堆结构

基于桶的排序

定义适当的桶，数组放入符合的桶中，然后根据规则取出桶中的数据即可排序

不基于比较的排序都是根据数据状况来定制，没有选择性排序的通用性

1. 计数排序

词频统计，遍历数组后，词频数组保存个数，根据词频数组还原数组后得到排序后的数组

2. 基数排序

• 准备0-9十个桶，桶多为队列结构
• 从低位到高位遍历：
  • 个位：进桶，出桶，得到新顺序数组
  • 十位：新数组基础上，进桶，出桶
  • ......
  • N位

二、 链表

常见问题总结：

1. 逆向链表

2. 打印两个链表的公共部分

3. 判断一个链表是否为回文结构

4. 对链表根据某数分区

5. 链表节点含有随机指针，复制该链表

6. 两链表相交，求相交的第一个节点：

   • 判断链表是否有环
   • 有环，求入环节点

三、树

树的常见分类：

### 完全二叉树

满二叉树

二叉搜索树

平衡二叉树

四、图

图的表示