9.9.4 快速排序优化
刚才讲的快速排序还是有不少可以改进的地方，我们来看一些优化的方案。
试想一下，我们对数组{9,1,5,8,3,7,4,6,2}，取左9，中3，右2来比较，使得L.r[low]=3，一定要比9和2要来得更为合理。
三数取中对小数组来说有很大的概率选择到一个比较好的pivotkey，但是对于非常大的待排序的序列来说还是不足以保证能够选择出一个好的pivotkey，因此还有个办法是所谓九数取中（median-of-nine），它是先从数组中分三次取样，每次取三个数，三个样品各取出中数，然后从这三个中数当中再取出一个中数作为枢轴。显然这就更加保证了取到的pivotkey是比较接近中间值的关键字。有兴趣的同学可以自己去实现一下代码，这里不再详述了。
2. 优化不必要的交换
观察图9-9-1～图9-9-6，我们发现，50这个关键字，其位置变化是1→9→3→6→5，可其实，它的最终目标就是5，当中的交换其实是不需要的。因此我们对Partition函数的代码再进行优化。
3. 优化小数组时排序方案
对于一个数学科学家，博士生导师，他可以攻克世界性的难题，可以培养最优秀的数学博士，但让他去教小学生“1+1=2”的算术课程，那还真未必会比常年在小学学校里耕耘的数学老师教得好。换句话说，大材小用有时会变得反而不好用。刚才我谈到了对于非常大的数组的解决办法。那么相反的情况，如果数组非常小，其实快速排序反而不如直接插入排序来得更好（直接插入是简单排序中性能最好）。其原因在于快速排序用到了递归操作，在大量数据排序时，这点性能影响相对于它的整体算法优势而言是可以忽略的，但如果数组只有几个记录需要排序时，这就成了一个大炮打蚊子的大问题。因此我们需要改进一下QSort函数。
我们增加了一个判断，当high-low不大于某个常数时（有资料认为7比较合适，也有认为50更合理，实际应用可适当调整），就用直接插入排序，这样就能保证最大化的利用两种排序的优势来完成排序工作。
4. 优化递归操作
大家知道，递归对性能是有一定影响的，QSort函数在其尾部有两次递归操作。如果待排序的序列划分极端不平衡，递归的深度将趋近于n，而不是平衡时的log2n，这就不仅仅是速度快慢的问题了。栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。因此如果能减少递归，将会大大提高性能。
于是我们对QSort实施尾递归优化。来看代码。
当我们将if改成while后（见高亮代码部分），因为第一次递归以后，变量low就没有用处了，所以可以将pivot+1赋值给low，再循环后，来一次Partition(L,low,high)，其效果等同于“QSort(L,pivot+1,high);”。结果相同，但因采用迭代而不是递归的方法可以缩减堆栈深度，从而提高了整体性能。
在现实的应用中，比如C++、java、PHP、C#、VB、Javascript等等都有对快速排序算法的实现 ，实现方式上略有不同，但基本上都是在我们讲解的快速排序法基础上的精神体现。