快速排序与归并排序的区别

• 快速排序：选择一个数组元素作为划分依据
  划分工作量：$O(n)$
  合并工作量：$O(1)$
  子问题工作量：$T(n/2)$
  最好时间复杂度：$T(n) = 2T(n/2) + O(n)$ 解得：$T(n) = O(n\log{n})$
  最坏时间复杂度：$O(n^2)$
  稳定性：不稳定
• 归并排序：选择数组下标的中间值作为划分依据
  划分工作量：$O(1)$
  合并工作量：$O(n)$
  子问题工作量：$T(n/2)$
  最好时间复杂度：$T(n) = 2T(n/2) + O(n)$ 解得：$T(n) = O(n\log{n})$
  最坏时间复杂度：$T(n) = O(n\log{n})$
  稳定性：稳定
  稳定与不稳定解释：如对｛2，3，5，5，5，7｝排序
  稳定：排序后第一个5永远在第三个位置上
  不稳定：排序后第一个5可能出现在第3，4，5个位置上