php快速排序算法

wxsheng

　　第一种实现，从数组一头便利，平均时间复杂度nlog(n)，极端情况下，数组为倒序，此时时间复杂度退化成n2。

• function quick_sort(&$arr, $lower, $upper)
  
• {
  
•     if($lower >= $upper)
  
•     {
  
•         return;
  
•     }
  
• 
  
•     $key = $arr[$lower];
  
•     $m = $lower;
  
•      
  
•     for($i = $lower + 1; $i = $upper)
  
•     {
  
•         return;
  
•     }   
  
• 
  
•     $key = $arr[$lower];
  
•     $i = $lower;
  
•     $j = $upper;
  
• 
  
•     while($i < $j)
  
•     {
  
•         while($arr[++$i] < $key && $i < $j);
  
•         while($arr[--$j] > $key);
  
• 
  
•         if($i > $j)
  
•         {
  
•             break;
  
•         }
  
• 
  
•         $tmp = $arr[$j];
  
•         $arr[$j] = $arr[$i];
  
•         $arr[$i] = $tmp;
  
•     }
  
•      
  
•     $tmp = $arr[$j];
  
•     $arr[$j] = $arr[$lower];
  
•     $arr[$lower] = $tmp;
  
• 
  
•     quick_sort($arr, $lower, $j - 1);
  
•     quick_sort($arr, $j + 1, $upper);
  
• }