前幾天同僚提到一個問題，為什麼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
![[轉]ISUP信令的IAM消息詳細内容[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)