快速排序

第 1 节到第 6 节是「快速排序」的内容，希望我这样的编排，读者能够感受到一点一点、层层递进，为了解决问题，而引入的逐步优化。

并且通过多次练习，掌握写对「快速排序」也不需要背代码，而是科学、合理地设计「循环不变量」，明确地知道每一个变量 的含义，进而把代码写对。

归并排序与快速排序都使用了「分治思想」

归并排序

• 拆分：不管数组的形态，总是将数组一分为二；
• 组合：合并两个有序的数组。

快速排序

• 拆分：根据某个元素 pivot，将数组整理成两个部分；

  • 前半部分小于 pivot， 后半部分大于等于 pivot；
  • 把 pivot 交换到前半部分的最后一个元素。

• 组合：什么都不用做。