Quick Sort - 快速排序
核心：快排是一种采用分治思想的排序算法，大致分为三个步骤。
- 定基准——首先随机选择一个元素最为基准
- 划分区——所有比基准小的元素置于基准左侧，比基准大的元素置于右侧，
- 递归调用——递归地调用此切分过程。
先来一张动图看看快速排序的过程。
- 选中
3作为基准 lo指针指向元素6,hi指针指向4, 移动lo直至其指向的元素大于等于3, 移动hi直至其指向的元素小于3。找到后交换lo和hi指向的元素——交换元素6和2。lo递增，hi递减，重复步骤2，此时lo指向元素为5,hi指向元素为1. 交换元素。lo递增，hi递减，发现其指向元素相同，此轮划分结束。递归排序元素3左右两边的元素。
与归并排序的区别：
- 归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序。递归调用发生在处理整个数组之前。
- 快速排序将一个数组分成两个子数组并对这两个子数组独立地排序，两个子数组有序时整个数组也就有序了。递归调用发生在处理整个数组之后。
Robert Sedgewick 在其网站上对 Quicksort 做了较为完整的介绍，建议去围观下。