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;
	}
}