php 快速排序函數 使用教程

在php編程中會用到一些常用的算法，把這些算法代碼寫成函數方便以後調用^_^。php快速排序函數就這樣誕生了，兩個版本，遞歸和無遞歸。可以根據實際需要選用。

/*
* qsort 數據快速排序遞歸版
*
* $array_to_sort 需要排序的數組
* 排序過程中，數組的鍵會被替換為數字索引的鍵
* 如果$array_to_sort不是數組返回false
* 排序成功返回true
*
* $lvl為遞歸深度
*
*/
function qsort( &$array_to_sort, $btm=null, $top=null, $lvl=0 )
{
// check if top of recursion and do checks
// otherwise the checks slow down the recursion
if ( $lvl == 0 )
{
if ( !is_array($array_to_sort) )
{ return false; }
// yank all the values out to prevent incorrect keying
$array_to_sort = array_values($array_to_sort);

$btm=0;
$top=count($array_to_sort)-1;
}

$lo = $btm;
$hi = $top;
$pivot = $array_to_sort[$hi];

// throw highs and lows to each side of the element
// and the one element will be in the correct position,
// then array is already partially sorted
while ( $lo < $hi )
{
while ( $lo < $hi && $pivot > strval($array_to_sort[$lo]) )
{ $lo++; }
if ( $lo != $hi )
{ swap( $array_to_sort[$lo], $array_to_sort[$hi] ); }

while ( $lo < $hi && strval($array_to_sort[$hi]) > $pivot )
{ $hi--; }
if ( $lo != $hi )
{ swap( $array_to_sort[$lo], $array_to_sort[$hi] ); }
}

// now $lo and $hi are on the sorted element

if ( $lo-1 > $btm ) // if equal, there is only one sorted element
{ qsort($array_to_sort, $btm, $lo-1, $lvl+1); }

if ( $top > $lo+1 ) // see last comment
{ qsort($array_to_sort, $lo+1, $top, $lvl+1); }
return true;
}

/* Author: JBLamer, Date: 20070322
*
* qsort0 數組快速排序非遞歸版
*
* 參數用法同上
*/
function qsort0( &$array_to_sort )
{
if ( !is_array($array_to_sort) )
{ return false; }

// yank all the values out to prevent incorrect keying
$array_to_sort = array_values($array_to_sort);

// record where we are via stack
$track_sort = array();

array_push($track_sort, array(0, count($array_to_sort)-1));

while ( count($track_sort) > 0 )
{
$hold = array_pop($track_sort);
$lo = $hold[0];
$hi = $hold[1];

$pivot = $array_to_sort[$hi];
// throw highs and lows to each side of the element
// and the one element will be in the correct position,
// then array is already partially sorted
while ( $lo < $hi )
{
while ( $lo < $hi && $pivot > strval($array_to_sort[$lo]) )
{ $lo++; }
if ( $lo != $hi )
{ swap( $array_to_sort[$lo], $array_to_sort[$hi] ); }

while ( $lo < $hi && strval($array_to_sort[$hi]) > $pivot )
{ $hi--; }
if ( $lo != $hi )
{ swap( $array_to_sort[$lo], $array_to_sort[$hi] ); }
}

// now $lo and $hi are on the sorted element

if ( $lo-1 > $hold[0] ) // if equal, there is only one sorted element
{ array_push($track_sort, array($hold[0], $lo-1)); }

if ( $hold[1] > $lo+1 ) // see last comment
{ array_push($track_sort, array($lo+1, $hold[1])); }
}
return true;
}

// this function is to swap element a with b
if ( !function_exists('swap') )
{
function swap( &$a, &$b )
{
$h = $a;
$a = $b;
$b = $h;
}
}