文章目录

• 1.快排
• • • 快排的思想就是＂分而治之＂．找到一个分区点，然后将小的放在前面，大的放在后面，分区点放在中间．最后发现待排序的区间变为1时停止．
• 2. 堆排序（完全二叉树形数据结构）
• • • 如何实现一个堆？
    • 插入元素
    • • • 从下往上
    • 删除堆顶元素
    • • • 从上往下（其实就是把节点从上面往下堆化）
    • 如何基于堆实现排序？(两步：建堆与排序)
    • • • 1. 建堆
        • 2.排序(O(n))
    • 提问：为什么它与快排的时间复杂度相同，但是快排就是比它要性能好呐？
• 3.冒泡与选择
• • • 冒泡：冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个数据进行比较，如果前者比后者大，就互相交换，最后就会找到一个最大的落在数组最后．重复以上工作ｎ次即可完成排序．
    • 选择：每次找到最小的一个元素放到已经排好序的数组的尾部即可．
• 2.插入
• • • 就是将后面的数据与前面的数据进行相比，如果小的话就将前面的数据向后移动，然后将其插入即可．
• 4. 拓扑排序(与图有关,图用(逆)邻接表存储)
• • (1)Kahn 算法
  • (2)DFS 算法
• 5.
• 6.
• 7.几道排序题目：
• • • (1)148. 排序链表
    • • • 考虑到O(nlogn)的排序算法有归并，快排，堆排．这里直接使用归并排序．
    • (2)