归并排序（Merge Sort）

• 思想说明
  1. 归并排序包含两种操作，一种是元素的比较，一种是元素的移动
  2. 使用分治思想，分而治之，将一个大问题分解成小的字问题来解决
  3. 将数组从中间分成前后两部分，并对前后两部分分别排序
  4. 不断重复 b，直到数组分解完成（归）
  5. 将排好序的两部分合并在一起（并）
• 分析
  1. 空间复杂度 O（n log(n)），不是原地排序算法
  2. 最好、最坏、平均时间复杂度均为 O（n log(n)）
  3. 不是稳定的排序算法

快速排序（Quick Sort）

• 思想说明
  1. 快速排序包含两种操作，一种是元素的比较，一种是元素的移动
  2. 选择数组中的任意一个元素作为 pivot（分区点）
  3. 遍历数组，将小于 pivot 的元素放在左边，将大于 pivot 的元素放在右边，pivot 放在中间，此时数组分成了三个部分
  4. 不断重复 2，直到区间缩小为 1
• 分析
  1. 空间复杂度 O（1），是原地排序算法
  2. 最好时间复杂度 O（n log(n)），最坏时间复杂度 O（n^2）（概率很小），平均时间复杂度 O（n log(n)）
  3. 是稳定的排序算法

堆排序

堆 Heap