这篇文章是基于已经基本了解快排及其思想的人而设定的，不清楚快排基本思想和各种简单排序的同学可以先谷歌一下。
正文：
最简单的优化方法，基准值的选取。
基准值的选取影响到分治程度和递归深度，所以对快排来说极其重要，取到最是靠中间的数快排的效率就越高。一般来说快排基准值的选取包括取固定位置（纯粹靠运气），取随机位置（在部分有序是效率高）。
我这里想到的方法也类似，首先input的时候会有first 和last，last - first越大基准值的选取就越重要，因为一旦选错了递归层数就相当深了，数据量大的时候很容易溢出栈，所以我的设定是随机选取数量级的万分之一的数取中位数，要是数量级少于30000就只选3个取中位数。这样就可以很大程序优化基准值了。
第二个优化，当序列长度分割到一定程度改为使用插入排序：
这里很容易理解为什么要改变排序方式，但是为什么是插入排序呢，因为快排的性质是把数字类型分割，所以一旦分割到一定程度，我这里认为数量级为16,序列之间是相对有序的，这种相对有序的数列是十分适合插排的，这个跟希尔排序的原理是一样的。
第三个优化，优化递归：
快排最大的优势来自递归，最大的缺憾也源自递归，只要递归做的不好，快排就会发生很多错误，所以最容易想到的就是优化递归。我这里用的是尾递归优化方法。也就是也是像快排那样把序列用基准值分为两部分递归，但是后面那部分不是直接拿去递归而是再用新的基准值分割，这样一直分割后面的部分。这样就可以把O(n)的堆栈深度和递归层数缩减到O(logn)了。
最后一个优化是剔除重复元素，是一种特殊化的优化：
很多大规模数列里面都包含很多相同元素，对于普通的快排来说，它不会区分这些相同的元素，也会给他们继续递归，这样其实很影响效率。特别是做游戏数据库的那种，几百万个数据几乎都挤在1到100的小区间里，这样相同的元素就相当多了。
我第一个想到的想法是用哈希表存储相同的元素数据，如果是上述的这样情况当然是可行的，而且相当好，但是要是遇到没有重复元素的序列那就白白牺牲了O(n)的空间复杂度了。所以我后来想到一个更好的方法，就是在快排开始分治，要把比k大和比k小的元素交换的时候多做一步判断，这个元素与k是否相等，如果是，那就把k与队尾的元素交换（这个过程是用来存储的），然后当两个指针重合的时候把刚才那些存储的重复元素再拿回来放在中间，这个时候只要递归除了中间重复元素之外的两边就行了。最妙的是这个存储重复元素的过程是不会添加快排的时间复杂度的，因为它本身也是给k排序的过程，所以最后就省下这一步了。
void QSort(int arr[],int low,int high)
{
int first = low;
int last = high;
int left = low;
int right = high;
int leftLen = 0;
int rightLen = 0;
if (high - low + 1 < 10)
{
InsertSort(arr,low,high);
return;
}
//一次分割
int key = SelectPivotMedianOfThree(arr,low,high);//使用三数取中法选择枢轴
while(low < high)
{
while(high > low && arr[high] >= key)
{
if (arr[high] == key)//处理相等元素
{
swap(arr[right],arr[high]);
right--;
rightLen++;
}
high--;
}
arr[low] = arr[high];
while(high > low && arr[low] <= key)
{
if (arr[low] == key)
{
swap(arr[left],arr[low]);
left++;
leftLen++;
}
low++;
}
arr[high] = arr[low];
}
arr[low] = key;
//一次快排结束
//把与枢轴key相同的元素移到枢轴最终位置周围
int i = low - 1;
int j = first;
while(j < left && arr[i] != key)
{
swap(arr[i],arr[j]);
i--;
j++;
}
i = low + 1;
j = last;
while(j > right && arr[i] != key)
{
swap(arr[i],arr[j]);
i++;
j--;
}
QSort(arr,first,low - 1 - leftLen);
QSort(arr,low + 1 + rightLen,last);
}
最后的数据比较：
其实我最后还想到两个不错的优化，就是当递归层数太深的时候可以用STL库里的部分排序partial_sort，还有分治的过程也可以用STL的那个partition分类排序优化，但是你要跟人家的STL库sort()比快，又调用人家的库感觉有点不厚道，所以就没用了。
最后，我把自己优化的代码跟各种标准库的sort比较效率，发现都是大同小异，唯独遇到VS2010的时候，VS的sort速度竟然是我快排的十倍以上，我十分诧异，毕竟我的快排效率是跟STL模板库同一个等级的。我马上就去看VSsort的源码了，发现看不懂。。。后来查了一下，才发现VS的排序跟我们排序的方式并不相同，他是把vector里面的本质萃取出来，取消了vector在++时候的边界检查并且把迭代器当指针来用，所以才会快这么多的。