请教一个快速排序法的问题-php教程-PHP中文网

请教一个快速排序法的问题

php中文网

发布： 2016-06-23 13:44:59

原创

1134人浏览过

无涯·问知

无涯·问知，是一款基于星环大模型底座，结合个人知识库、企业知识库、法律法规、财经等多种知识源的企业级垂直领域问答产品

查看详情

回复讨论(解决方案)

$base_num 不会被覆盖，
这与 php 的变量作用域有关，函数内的变量只在本函数内有效
也就是说，递归调用的 quick_sort 中的 $base_num 都是独立的
这一点与 js 不同，需要注意。当然 js 中可用 var 声明局部变量

每次执行都是函数体内的局部变量，除非是静态或全局变量才会改变

你的意思是，我举个例子，比如：3,1,5,4
第一次穿进去把3拿出来做标尺，1,5,4以此和它做对比，小于它的在left数组，大于它的在right数组，$left=array(1); $right=array(5,4);
当$right再次递归时候，把5拿出来做标尺，4和它对比。那被做标尺的值3和5最后能在最后一行代码
return array_merge($left_array, array($base_num), $right_array);中找到，是这样吧。

这样看的清楚点

print_r(quick_sort(array(6,1,5,8,7,4,2,3,0)));function quick_sort($arr) {	//先判断是否需要继续进行	$length = count($arr);	if($length <= 1) {		return $arr;	}	//如果没有返回，说明数组内的元素多于 1 个，需要排序	//选择一个标尺	//选择第一个元素	$base_num = $arr[0];	//遍历 除了标尺外所有元素，按照大小关系放入两个数组内	//初始化两个数组	$left_array = array(); //小于标尺的	$right_array = array(); //大于标尺的	for($i=1; $i<$length; $i++) {		if($base_num > $arr[$i]) {			//放入左边数组			$left_array[] = $arr[$i];		} else {			//放入右边数组			$right_array[] = $arr[$i];		}	}printf("in[%s] B[%d] L[%s] R[%s]<br>", join(',', $arr), $base_num, join(',', $left_array), join(',', $right_array));	//再分别对 左边 和 右边 得得数组进行相同的排序处理	//递归调用这个函数，并记录结果	$left_array = quick_sort($left_array);	$right_array = quick_sort($right_array);	//合并左边、标尺、右边	return array_merge($left_array, array($base_num), $right_array);}

登录后复制

in[6,1,5,8,7,4,2,3,0] B[6] L[1,5,4,2,3,0] R[8,7]in[1,5,4,2,3,0] B[1] L[0] R[5,4,2,3]in[5,4,2,3] B[5] L[4,2,3] R[]in[4,2,3] B[4] L[2,3] R[]in[2,3] B[2] L[] R[3]in[8,7] B[8] L[7] R[]Array ( [0] => 0 [1] => 1 [2] => 2 [3] => 3 [4] => 4 [5] => 5 [6] => 6 [7] => 7 [8] => 8 )

登录后复制

这样看的清楚点

print_r(quick_sort(array(6,1,5,8,7,4,2,3,0)));function quick_sort($arr) {	//先判断是否需要继续进行	$length = count($arr);	if($length <= 1) {		return $arr;	}	//如果没有返回，说明数组内的元素多于 1 个，需要排序	//选择一个标尺	//选择第一个元素	$base_num = $arr[0];	//遍历 除了标尺外所有元素，按照大小关系放入两个数组内	//初始化两个数组	$left_array = array(); //小于标尺的	$right_array = array(); //大于标尺的	for($i=1; $i<$length; $i++) {		if($base_num > $arr[$i]) {			//放入左边数组			$left_array[] = $arr[$i];		} else {			//放入右边数组			$right_array[] = $arr[$i];		}	}printf("in[%s] B[%d] L[%s] R[%s]<br>", join(',', $arr), $base_num, join(',', $left_array), join(',', $right_array));	//再分别对 左边 和 右边 得得数组进行相同的排序处理	//递归调用这个函数，并记录结果	$left_array = quick_sort($left_array);	$right_array = quick_sort($right_array);	//合并左边、标尺、右边	return array_merge($left_array, array($base_num), $right_array);}

登录后复制

in[6,1,5,8,7,4,2,3,0] B[6] L[1,5,4,2,3,0] R[8,7]in[1,5,4,2,3,0] B[1] L[0] R[5,4,2,3]in[5,4,2,3] B[5] L[4,2,3] R[]in[4,2,3] B[4] L[2,3] R[]in[2,3] B[2] L[] R[3]in[8,7] B[8] L[7] R[]Array ( [0] => 0 [1] => 1 [2] => 2 [3] => 3 [4] => 4 [5] => 5 [6] => 6 [7] => 7 [8] => 8 )

登录后复制

这样看的清楚点

print_r(quick_sort(array(6,1,5,8,7,4,2,3,0)));function quick_sort($arr) {	//先判断是否需要继续进行	$length = count($arr);	if($length <= 1) {		return $arr;	}	//如果没有返回，说明数组内的元素多于 1 个，需要排序	//选择一个标尺	//选择第一个元素	$base_num = $arr[0];	//遍历 除了标尺外所有元素，按照大小关系放入两个数组内	//初始化两个数组	$left_array = array(); //小于标尺的	$right_array = array(); //大于标尺的	for($i=1; $i<$length; $i++) {		if($base_num > $arr[$i]) {			//放入左边数组			$left_array[] = $arr[$i];		} else {			//放入右边数组			$right_array[] = $arr[$i];		}	}printf("in[%s] B[%d] L[%s] R[%s]<br>", join(',', $arr), $base_num, join(',', $left_array), join(',', $right_array));	//再分别对 左边 和 右边 得得数组进行相同的排序处理	//递归调用这个函数，并记录结果	$left_array = quick_sort($left_array);	$right_array = quick_sort($right_array);	//合并左边、标尺、右边	return array_merge($left_array, array($base_num), $right_array);}

登录后复制

in[6,1,5,8,7,4,2,3,0] B[6] L[1,5,4,2,3,0] R[8,7]in[1,5,4,2,3,0] B[1] L[0] R[5,4,2,3]in[5,4,2,3] B[5] L[4,2,3] R[]in[4,2,3] B[4] L[2,3] R[]in[2,3] B[2] L[] R[3]in[8,7] B[8] L[7] R[]Array ( [0] => 0 [1] => 1 [2] => 2 [3] => 3 [4] => 4 [5] => 5 [6] => 6 [7] => 7 [8] => 8 )

登录后复制

这个很直观！谢谢~