轻松学习快速排序（二 ）-- 快速排序优化

在上一篇文章轻松学习快速排序（一 ） -- 基本的快速排序中介绍了快速排序的算法，末尾提出了一个问题：例如这样的一个数组：1 10 23 6 9 10，一般来说会选择数组的第一个元素（也就是1）作为基准点，很显然以数组的第一个元素1作为基准点，本来1就是这个数组中最小的一个数，那么排序未达到预期的效果。如何来来选择这个基准点呢？一般来说，所选择的这个数最好是位于这个排序区间内所有数字的中间（也就是中位数），这样排序效果会最好。接下来，将会给出快速排序优化的两种方式：三数取中法和小区间优化。

基本思想：选择这组数据的第一个元素、中间的元素、最后一个元素，并在这三个数中取中间的元素作为基准点。比如有这样一组元素：1 10 23 6 9 10 ，第一个元素、中间的元素。最后一个元素分别为：1，23，10，那么这个中位数应该10。

选取中位数的实现代码如下：

 下面的代码只不过是一些无聊的逻辑判断，如果某个数M是中位数，那么有 L <= M <= R，实际上上面的代码就是按照这种特性来进行判断的。

 当划分的子区间的元素个数很小的时候（一般为十几个，比如说13个），使用插入排序比快速排序更加的高效。因为如果区间的元素个数为13时，此时再继续进行划分的话，区间会比较小。下面的代码是简单的插入排序的实现：