快速排序算法及分析

快速排序Quick Sort

• 快速排序的思路是依据一个“中值”数据项来把数据表分为两半：小于中值的一半和大于中值的一半， 然后每部分分别进行快速排序（ 递归）
  • 如果希望这两半拥有相等数量的数据项，则应该找到数据表的“中位数”但找中位数需要计算开销！要想没有开销，只能随意找一个数来充当“中值”比如，第1个数。

算法思路

快速排序的递归算法“递归三要素”如下

• 基本结束条件：数据表仅有1个数据项，自然是排好序的
• 缩小规模：根据“中值”， 将数据表分为两半， 最好情况是相等规模的两半
• 调用自身：将两半分别调用自身进行排序（ 排序基本操作在分裂过程中）