下面为一段普通的快速排序代码

（1）随机性

快速排序算法有较坏的情况，例如9、8、7、6、5、4、3、2、1这样一个序列，此时用快速排序则效率很低。

因此，可以编写shuffle函数打乱数组。

shuffle函数

（2）采用三向切分

在实际应用中，数组中可能存在着大量的重复元素，对重复元素进行排序没有任何意义。Dijkstra的三向切分解法思想如下图所示。他使用了lt和gt指针，令[lo,...,lt-1]的元素都下于v，[gt+1,...,hi]的元素都大于v。

1、a[i]<v , swap(a[lt],a[i]) , lt++ , i++

2、a[i]>v , swap(a[gt],a[i]) , gt--

3、a[i]==v , i++

三项切分思想

下图为三向切分处理数组的过程：

（3）小规模数组采用直接插入排序

在快速排序递归的过程中，处理小规模数组时，需要多次的递归，执行更小的数组，导致此时快速排序没有直接插入排序的效率高。因此将sort()中语句

if (hi <= lo) return;

替换成下面这条语句：

if ( hi <= lo + M) { Insertion.sort(a, lo, hi); return;}

其中M的最佳取值需要根据具体环境而定。

（4）设置哨兵

在插入排序时，在数组0号元素存放哨兵，可以去除判断指针是否小于数组的最低位的判断。

（5）个人想法

在之前的学习中，学过归并排序，它的复杂度为O(nlogn)，但是快速排序优化不采用归并排序而采用三向切分，个人有以下两点想法：

1、归并排序对重复数据的处理性能不稳定。通过测试，随机数组长度为100000000，数字范围为[0,200)，自顶向下的归并排序消耗时间为14427ms，三向切分消耗时间为13000ms。

2、小数组采用直接插入排序时，M的取值在5~15之间性能较好，此时若对直接插入排序采用归并，意义不大，可能还会因为递归导致效率降低。

（6）代码实现