快速排序的优化

在今年的毕业生就业经验交流会上，听到一位师兄分享自己的面试心得。其中有一个面试官的问题是（好像是阿里的），如何优化快排算法？

在这里整理一下我的看法和答案。

快速排序的基本思想：

快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

快速排序的三个步骤：

(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