快速排序的实现过程：

• 先从数列中选取一个元素作为基准数 (key)
• 扫描数列，将比基准数小的元素全部放到它的左边，大于或等于基准数的元素全部放到它的右边，得到左右两个区间
• 再对左右区间重复第二步，直到各区间元素个数少于两个。 其实这个就是一个分治的过程，类似于 二叉树的遍历。
• 非递归的方式其实就是用数据结构栈模拟递归过程，单趟的排序是一样的。

单趟排序有三种实现思想
1.hoare思想
2.挖坑法
3.前后指针法

hoare思想

• 让begin从前往后找比基准值大的元素，找到之后停止；让end从后往前找比基准值小的元素，找到之后停止；如果begin和end没有相遇：将begin位置上的元素和end位置上的元素进行交换；循环结束后将基准值和begin位置上的元素进行交换。

• 三数取中
• 小区间使用插入排序优化

三数取中

小区间优化

当区间比较小的时候，就不再递归划分去排序这个小区间。可以考虑其他排序。
这里建议直接用插入排序。