前几天同事提到一个问题，为什么lua中table.sort中的第二个参数在相等的情况下必须要返回false，而不能返回true?
当时一下没反应过来，我就记得要返回false，具体为什么竟一时无语。
在lua中table.sort使用的的快速排序。
于是再次温习快速排序 记录如下。
(参考http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F ,
http://zh.wikipedia.org/wiki/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95
http://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8)
基本的快速排序的核心思想就是一句话：找一个参考点(枢点)，比我大得扔右边，比我小的扔左边。
(P.S.在这里为了实现方便我都使用vector来替代数组 [] , 这里只是为了原理分析,实际情况中使用什么视情况而定,也并没有考虑效率问题)
先定义辅助函数：
void prtvector( const vector<int>& v )
{
for( int i = 0; i < v.size(); ++i )
{
printf( "%d ", v[i] );
}
printf( "\n" );
}
void swap( vector<int>& in, int a , int b )
{
if ( a == b )
{
return;
}
int t = in[a];
in[a] = in[b];
in[b] = t;
}
bool less_than_int( int a , int b )
{
return a < b;
};
基于快速排序的核心思想于是有了第一种简单粗暴的写法:
vector<int> concatenate( vector<int>& left , int pivot , vector<int>& right)
{
vector<int> ret;
if ( ! left.empty() )
{
ret.insert( ret.end(), left.begin(),left.end() );
}
ret.push_back( pivot );
if ( ! right.empty() )
{
ret.insert( ret.end(),right.begin(),right.end() );
}
return ret;
}
vector<int> quick_sort_1( vector<int>& in )
{
if (in.size() <= 1)
{
return in;
}
int p = in.size() / 2; //初始枢点
int pivot = in[p]; //枢点值
vector<int> left;
vector<int> right;
/*遍历把小于枢点的扔到left，反之扔到right*/
for ( int i = 0; i < in.size(); ++i )
{
if ( i == p ) //跳过枢点
{
continue;
}
if ( less_than_int( in[i] , pivot ) )
{
left.push_back( in[i] );
}
else
{
right.push_back( in[i] );
}
}
//枢点不用继续参与排序
return concatenate( quick_sort_1(left) , pivot , quick_sort_1(right) ); //连接左边和枢点和右边
}
这种实现缺陷很明显，每次都需要额外的分配很多内存来存储(Ω(n))
要改进快速排序就要提到in-place算法的概念,于是快速排序基于原地算法有了第二种实现:
//分割函数
int partition( vector<int>& in,int left,int right,int pivotindex)
{
int pivot = in[pivotindex];
swap( in, pivotindex, right ); //枢点放至末尾
int storeindex = left;
for ( int i = left; i < right; ++i )//从左至右单向的遍历
{
/*如果当前值比枢点小,那么把这个值和记录点交换*/
if ( less_than_int( in[i] ,pivot ) )
{
swap( in , storeindex , i );
++storeindex;
}
}
swap( in,right , storeindex ); /*最终得到在枢点左边的比枢点小,在枢点右边的比枢点大*/
return storeindex;
}
void quick_sort_2( vector<int>& in, int left , int right )
{
if ( right > left )
{
int p = in.size() / 2; //选择枢点
int pivotnew = partition( in , left, right ,p );
/*在左右两边分别递归,枢点不用继续参与排序*/
quick_sort_2( in,left,pivotnew-1 );
quick_sort_2( in,pivotnew+1,right );
}
}
在第二种方式的基础又衍生了另一种in-place的写法(双向遍历)：
<pre name="code" class="cpp">void quick_sort_3 (vector<int>& in, size_t left,size_t right)
{
int p = (left + right) / 2; //初始枢点
int pivot = in[p]; //枢点值
int i = left,j = right;
/*这里的实现并没有直接使用swap*/
/*p所在的位置相当于一个临时位置*/
for ( ; i < j;) {
/*从最左边开始遍历,如果i的值比枢点的值大 */
while (! (i>= p || less_than_int( pivot ,in[i] )))
++i;
if (i < p) {
in[p] = in[i];
p = i;
}
/*从最右边开始遍历,如果j的值比枢点的值小*/
while (! (j <= p || less_than_int(in[j] , pivot )))
--j;
if (j > p) {
in[p] = in[j];
p = j;
}
}
in[p] = pivot; //把枢点的值设回来。
if (p - left > 1)
quick_sort_3(in, left, p - 1); //递归枢点左边
if (right - p > 1)
quick_sort_3(in, p + 1, right);//递归枢点右边
};
这三种方式都体现了快速排序的核心思想:分而治之。
上面是快速排序的实现。接下来考虑:
我们假设如果 在相等的情况返回true，也就是
bool less_than_int( int a , int b )
{
return a <= b;
};
以上3种实现会怎样呢?
在quick_sort_3中 less(a,b)，less(b,a)同时使用，相等的情况下返回true，本来语意上就有问题，我比你大，你比我大，同时为真，明显有问题。实际情况中，如果同时为true那么当 出现in[j] == in[j] == pivot 情形时，将会陷入死循环，因为++i和--j都不会被执行，p 就在 i 和j 上陷入死循环。
在第一种实现和第二种实现中就不会出现这个问题，因为这两种实现中并没有同时使用到less(a,b)和less(b,a)的情况，每排序一次都会至少有一个元素被排序（枢点），所以这两种方式可以让排序在有限的次数内完成。因此这两种实现方式是可以在两个元素相等的情形下返回true的。
接下来就来讨论最初的问题：为什么lua中table.sort中的第二个参数在相等的情况下必须要返回false，而不能返回true?
table.sort( table [ , func ] ); 第2个参数为一个函数，定义了就相当于我们的less_than函数。
在Ltablib.c的sort函数中我们看到lua实际使用auxsort函数实现了lua的排序。接下来我把它翻译为C++语言实现：
void auxsort( vector<int>& in,int l, int u )
{
while( l < u ) /*为什么是while,稍候解释!*/
{
int i,j;
//先对 左 中 右 3个值排序
if ( less_than_int( in[u] , in[l] ) )
{
swap( in,u,l );
}
if ( u - l == 1 ) break; //只有两个
i = (u+l) / 2;
if ( less_than_int(in[i] , in[l]) )
{
swap(in,i,l);
}
else
{
if ( less_than_int( in[u] ,in[i] ) )
{
swap( in , u , i );
}
}
if ( u - l== 2 ) break;//只有三个
/*至此，左中右三个值已经是有序的了in[l] <= in[i] <= in[u]*/
int pivotvalue = in[i]; //选择中点为枢点
/*把中点值和u-1交换, 此时有in[l]<=in[u-1]<=in[u],只需要对[l+1,u-2]之间的元素接着进行分区*/
swap( in , i , u - 1 );
i = l;
j = u - 1;
for(;;)
{
/*从左(l+1)至右遍历， 直到找到一个比枢点值大的i*/
while( ++i,less_than_int( in[i],pivotvalue ) )
{
if ( i > u )
{
assert( !"invalid order function for sorting" ); //lua error!
}
}
/*从右(u-2)至左遍历,直到找到一个比枢点值小的j*/
while( --j,less_than_int( pivotvalue, in[j] ) )
{
if (j < l)
{
assert( !"invalid order function for sorting" ); //lua error!
}
}
/*遍历完整个[l+1,u-2]时，结束循环*/
if ( j < i )
{
break;
}
/*把左边那比枢点值大的和右边找到的比枢点值小的交换*/
swap( in , i , j );
}
/*把枢点值放回i,至此i的左边都比in[i]小，i的右边比in[i]大，即:in[l..i-1]<=in[i]==P<=a[i+1..u]*/
swap( in, u-1,i );
/*至此分区(partition)结束*/
/*
*到这里了本来是对左右分区分别递归调用(auxsort)（即调用两次auxsort,可是这里却只调用了一次！
*这里用了一个技巧：尾递归(tail recursive)。
*首先比较左边和右边谁的分区更大 i-l 表示左边的分区的大小, u -i 表示右边的分区的大小
*对较小的分区进行递归(调用auxsort),对较大的分区采用尾递归(其实是尾递归对应的迭代，并不是真正意义上的尾递归,是一种思路)的方式。
*这样做的意义目测是:在一定程度上降低栈的深度,以缓解递归带来的栈溢出问题(stack over flow)
*/
if ( i - l < u - i )
{/*对[i+1,u]尾递归,[l,i-1]递归*/
j = l;i = i - 1;l = i + 2;
}
else
{/*对[l,i-1]尾递归,[i+1,u]递归*/
j = i + 1;i = u;u = j - 2;
}
auxsort( in , j , i ); //递归
}//尾递归
}
auxsort的翻译完完全全遵照了lua中的实现，对一些理解比较困难的地方也写了注释方便自己以后查阅。
如注释中所说，除了使用尾递归，其他的也就是和quick_sort_3没有太大区别(这里使用了swap而quick_sort_3没有)。
假设在比较函数中a b 相等时返回true，那么在分区的时候，在less_than( in[i] , pivotvalue )相等时返回true，那么会造成错误的++i调用（或--j）可能会导致：
1. 如果是在数组的边界 就会造成数组越界(对i处是大于size，对j处是小于0)，lua中表现为传入的比较参数为空值，func(a,b) 正常情况a，b都不会为空，但是如果在i处越界就会表现为func(nil,b),在j处越界就会表现为func(a,nil)
2. 如果是在数组的分区的边界 就会抛出 Invalid order function for sorting 错误
3.这种也是最隐晦的错误，因为lua将不会抛出错误，这会导致输出结果不正确。考虑以下情况当分区经过三点排序后为{ 1 2 1 3 }，
此时枢点选择为2，第一次交换{ 1 1 2 3 } 经过分区将得到分区点i = 3 交换回来{ 1 1 3 2 }，因为在枢点的最后一次比较中，就是自己和自己比较less( pivot , pivot ) 这里返回true，那么把枢点后面的一个值给换到枢点前面来，这也违背了快速排序的基本原则。
对于具体是哪一种错误将会受到元素本身的组成影响。所以当在lua中出现以上错误时，应该优先查看比较函数的是否有此类问题。
综上在快速排序中元素值相等时都应该尽量的返回false，一来这更符合我们的逻辑，二来将会避免不必要的错误。
P.S. :关于枢点的选择：
在快速排序中枢点的选择对快速排序的速度影响很大，但我们看到4中方案中都统一的采用了中点来作为枢点。 搜索了很久也没有找到相关的文章，但是我记得大学时的数据结构教材上好像说的是经验所得。
所以在没有更好的选择的情况下，我们都采用中点作为枢点的选择方案( low + high ) / 2