PHP 中实习快速排序算法(快速排序思想)

学习笔记 马富天 2017-11-05 13:54:30 77 0

【摘要】快速排序算法:递归分治的思想,是最常用的一种排序算法,速度快,效率高。

假设有一个数列:6,9,2,7,3,8,5,4,第一轮排序则:

以 6 位基数,将比 6 大的数放在 6 的右边,把 6 小的数放在 6 的左边,排序后在合并在一起,最后得到第一轮顺序的结果:

[2,3,5,4] 6 [9,7,8]

之后对 [2,3,5,4] 和 [9,7,8] 分别采用这样的方法进行排序,如对 [2,3,5,4] 进行排序,此时将 2 作为基数,将比 2 大的数放置在 2 的右边,比 2 小的数放置在 2 的左边,排序后是:

2 [3,5,4] 6 [7,8] 9

此时还需要排序的是 [3,5,4] 和 [7,8]

以同样的方法进行排序即可。这样的话,我们就可以写出一个递归函数来进行排序了。

完整代码如下:

  1. 	function quickSort(&$arr)
  2. 	{
  3. 		if(count($arr) > 1)
  4. 		{
  5. 			$k = $arr[0];	//	基数
  6. 			$left = array();	//	左边数组
  7. 			$right = array();	//	右边数组
  8. 			for($i = 1;$i < count($arr);$i ++)
  9. 			{
  10. 				if($arr[$i] > $k)
  11. 				{
  12. 					$right[] = $arr[$i];
  13. 				}else
  14. 				{
  15. 					$left[] = $arr[$i];
  16. 				}
  17. 			}
  18. 			$left = quickSort($left);
  19. 			$right = quickSort($right);
  20. 			return array_merge($left,array($k),$right);	//	合并,这里是 array($k) 而不是 $k。
  21. 		}else
  22. 		{
  23. 			return $arr;
  24. 		}
  25. 	}
  26. 	$arr = array(8,3,6,9,1,2);
  27. 	var_dump(quickSort($arr));

版权归 马富天PHP博客 所有

本文标题:《PHP 中实习快速排序算法(快速排序思想)》

本文链接地址:http://www.mafutian.net/340.html

转载请务必注明出处,小生将不胜感激,谢谢! 喜欢本文或觉得本文对您有帮助,请分享给您的朋友 ^_^

0

0

上一篇《 冒泡排序的基本思想 》 下一篇《 TCP 三次握手协议简介,为什么不是二次握手? 》

暂无评论

评论审核未开启
表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情
验证码

TOP10

  • 浏览最多
  • 评论最多