这篇文章主要介绍了PHP两种快速排序算法实例,本文直接给出实现代码,分别使用递归法、迭代法实现,需要的朋友可以参考下

虽然在PHP这样的web应用开发中，我们不是太强调排序的重要性，因为PHP自身已经带了例如sort()等这样强大的排序函数，但是在一些重要的场合，例如某些高并发的场合，我想排序算法的影响已经不能忽略。所以在此介绍递归排序和迭代排序。

递归法：

1. /** 
2. * 递归法实现的快速排序 
3. */ 
4. function quicksort($seq) 
5. { 
6.     $k = $seq[0]; 
7.     $x = array(); 
8.     $y = array(); 
9.     for($i=1; $i< $_size; $i++) { 
10.       if($seq[$i] <= $k) { 
11.         $x[] = $seq[$i]; 
12.       } else { 
13.         $y[] = $seq[$i]; 
14.       } 
15.     } 
16.     $x = quicksort($x); 
17.     $y = quicksort($y); 
18.     return array_merge($x, array($k), $y); 
19.   } else { 
20.     return $seq; 
21.   } 
22. } 

迭代法：

1. /** 
2. * 迭代法的快速排序 
3. */ 
4. function quicksortx(&$seq) 
5. { 
6.   $stack = array($seq); 
7.   $sort = array(); 
8.   while ($stack) { 
9.     $arr = array_pop($stack); 
10.     if(count($arr) <= 1) { 
11.       if(count($arr) == 1) { 
12.         $sort[] = &$arr[0]; 
13.       } 
14.       continue; 
15.     } 
16.     $k = $arr[0]; 
17.     $x = array(); 
18.     $y = array(); 
19.     $_size = count($arr); 
20.     for($i =1 ;$i < $_size; $i++) { 
21.       if($arr[$i] <= $k) { 
22.         $x[] = &$arr[$i]; 
23.       } else { 
24.         $y[] = &$arr[$i]; 
25.       } 
26.     } 
27.     !emptyempty($y) && array_push($stack, $y); 
28.     array_push($stack, array($arr[0])); 
29.     !emptyempty($x) && array_push($stack, $x); 
30.   } 
31.   return $sort; 
32. } 

使用：

1. /** 
2. *产生一个随机数组 
3. */ 
4. for($i=0;$i<5;$i++){ 
5.   $testArr[]=mt_rand(0,100); 
6. } 
7. var_dump($testArr); 
8. var_dump(quicksort($testArr)); 
9.  
10. var_dump(quicksortx($testArr));

Tags: PHP快速排序算法

分享到：