在今年的毕业生就业经验交流会上，听到一位师兄分享自己的面试心得。其中有一个面试官的问题是（好像是阿里的），如何优化快排算法？
在这里整理一下我的看法和答案。
快速排序的基本思想：
快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
快速排序的三个步骤：
(1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 “基准”（pivot）
(2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大
(3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。
优化的思想：
- 对寻找基准的方法进行优化 （标准的方式是 左边的第一个作为基准，但是还有更好的方法）
- 对递归进行优化 （使用尾递归的思想）
- 使用并行或多线程处理子序列
三种选择基准的方法：(3种)
方法1：固定位置
思想：取序列的第一个或最后一个元素作为基准
方法2：随机选取基准
思想：取待排序列中任意一个元素作为基准
方法3：三数取中（median-of-three）
举例：待排序序列为：8 1 4 9 6 3 5 2 7 0
左边为：8，右边为0，中间为6.
我们这里取三个数排序后，中间那个数作为枢轴，则枢轴为6
这三种方法里面，使用三数取中选择枢轴优势还是很明显的，但是还是处理不了重复数组。
方法二：并行或多线程处理子序列
利用多线程的思想
方法三：尾递归的思想
这是我网上看到的很多人说快排使用尾递归的思想，可以进行优化。但是看见很久，我个人感觉这个并不是尾递归的思想，只是普通的递归。
尾递归的定义是：
尾递归是用来优化递归算法空间复杂度的，其原理是当递归调用出现在函数的最后一步时，编译器就可以丢弃当前函数的调用帧，这样，整个递归过程中，就仅仅存在一个调用帧，这样就减小了内存的消耗。
但是下面的代码却是：
在进入第一次递归调用时，由于后续还要进行start=index+1;所以这个并不是尾递归的思想。
这是stackoverflow上面的对于这个问题的回答，他也认为快排没有办法使用尾递归进行优化：http://stackoverflow.com/questions/9247504/how-to-implement-tail-recursive-quick-sort-in-scala#comment11651078_9247504
网上流行的尾递归的快排代码
int Partition(int *p,int len,int start,int last)
{
int flag=*(p+start);
int i=start;
int j=last;
while(i<j)
{
while(i<j && *(p+j)>flag) --j;
*(p+i)=*(p+j);
while(i<j && *(p+i)<=flag) ++i;
*(p+j)=*(p+i);
}
*(p+i)=flag;
return i;
}
void QuickSort(int *p,int len,int start,int last)
{
if(NULL=p) return;
int index;
while(start<last)
{
index=Partition(p,len,start,last);
QuickSort(p,len,start,index-1); //尾递归
//QuickSort(p,len,index+1,last);
start=index+1;
}
} ```
关于数据结合和算法的其他文章：
这又是一个flag http://www.jianshu.com/p/1dc543da3897