软件设计师 知识点拾遗 算法设计与分析

1. 2016年上半年第64题和65题

  归并排序的基本过程如下所述：

• 分解：
  • 将待排序数组递归地分成两半，直到每个子数组只包含一个元素（此时默认有序）。
• 合并：
  将两个已排序的子数组合并为一个有序数组：
  • 比较两个子数组的首元素，取较小者放入结果数组；
  • 重复上述步骤，直到某一子数组被完全合并；
  • 将剩余子数组的元素直接追加到结果中。

---

2. 2015年上半年第62题和63题

​  ​优先队列是一种特殊的队列数据结构，其中每个元素都有一个关联的​​优先级​​。元素的出队顺序不是由插入时间决定，而是由优先级高低决定：​​优先级最高的元素最先出队​。而堆是一个很好的用来维护优先级的数据结构。每次插入都需要重新堆化，这一时间复杂度为O(lgn)。