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; } }
1 条评论
[...] This post was mentioned on Twitter by junichi_y, 热点风向标. 热点风向标 said: php 快速排序函数 http://ff.im/-uAC0t [...]