最基本：

    • 稳定冒泡排序：每一遍交换相邻的逆序元素对，来n遍
    • 稳定插入排序：逐个将元素放在合适的位置，放n次
      • 不稳定希尔排序：分组插入，gap递减一半（2i-1比2i好，减少了重复的比较），复杂度O(n1+§))
    • 不稳定选择排序：先选最小的放在第一个，选n次
      • 不稳定树形选择排序：n个叶子节点的完全二叉树，父节点值为左右子节点的最小数，使最小数选择过程的复杂度从N减小为logN
      • 不稳定堆排序：优化树形选择排序辅助空间多（非叶子节点）等缺点
        • 创建无序堆 -> 调整成最大堆 -> 交换堆顶至有序段，返回上一步
      • 不稳定鸡尾酒排序：每次将最小值放第一，最大值放最后，来n/2次

    稍进阶：

    • 桶【先分配后收集，非比较排序，复杂度不受NlogN限制】：
      • 计数排序：先获得待排序数据的范围，范围内一个数一个桶
      • 桶排序：每个桶存储一定范围的值，桶内利用链表排好序
      • 稳定基数排序：根据每一位的数字0-9分配桶
        • LSD：从最低位开始排，先分配后收集，每一趟对上一趟的结果进行操作
        • MSD：从最高位开始排，先分配，再桶内递归分配桶，最后收集起来
    • 【分治】
      • 稳定归并排序：逐次二分，后逐次归并
        • 递归调用
        • 迭代
      • 不稳定快速排序：
        • 优化1：小数组排序切换到插入排序
        • 优化2：选择合适的主元，左中右三数中位数作为主元
        • 优化3：重复元素处理

    外部排序：

    • 大文件的排序，即排序的记录存储在外存储器上，在排序过程中需进行多次的内、外存之间的交换。

    image.png

    序号 题目 备注

    - [x]

    | 56 | 合并区间 | 先排序（快排）后合并 | |
    - [x]

    | 57 | 插入区间 | 没什么好说的 | |
    - [x]

    | 75 | 颜色分类 | O(n)比较巧妙 类似多重桶排序 | |
    - [x]

    | 147 | | | |
    - [x]

    | 148 | | | |
    - [x]

    | 164 | 最大间距 | 桶排序&基数排序 可以做到O(n) | |
    - [ ]

    | 179 | | | |
    - [ ]

    | 220 | | | |
    - [ ]

    | 242 | | | |
    - [ ]

    | 274 | | | |
    - [ ]

    | 324 | | | |
    - [ ]

    | 349 | | | |
    - [ ]

    | 350 | | | |
    - [ ]

    | 524 | | | |
    - [ ]

    | 710 | | | |
    - [ ]

    | 767 | | | |
    - [ ]

    | 852 | | | |
    - [ ]

    | 922 | | | |
    - [ ]

    | 969 | | | |
    - [ ]

    | 973 | | | |
    - [ ]

    | 976 | | | |
    - [ ]

    | 1030 | | | |
    - [ ]

    | 1054 | | | |
    - [ ]

    | | | | |
    - [ ]

    | | | | |
    - [ ]

    | | | | |
    - [ ]

    | | | | |
    - [ ]

    | | | | |
    - [ ]

    | | | | |
    - [ ]

    | | | | |
    - [ ]

    | | | | |
    - [ ]

    | | | | |
    - [ ]

    | | | | |
    - [ ]

    | | | |