排序算法（4）快速排序-KeepStudy

排序算法（4）快速排序

>快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来，且在大部分真实世界的数据，可以决定设计的选择，减少所需时间的二次方项之可能性。

- 步骤：
    - 从数列中挑出一个元素，称为 “基准”（pivot），
    - 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
    - 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

```php
function quick_sort($array){
	if (count($array) <= 1) return $array;
	$key = $array[0];
	$left_arr = array();
	$right_arr = array();
	for ($i=1; $i<count($array); $i++){// 从索引的第二个开始遍历数组
	if ($array[$i] <= $key)// 如果值小于索引1
		$left_arr[] = $array[$i];// 装入左索引数组(小于索引1的数据)
	else
		$right_arr[] = $array[$i];// 否则装入右索引中(大于索引1的数据)
	}
	$left_arr = quick_sort($left_arr);
	$right_arr = quick_sort($right_arr);
	return array_merge($left_arr, array($key), $right_arr);
}
$array=array(1,3,6,2,4,8,5340,33,45,78,1000);
print_r(quick_sort($array));//Array ( 1 ,2 ,3 ,4 ,6 ,8 ,33,45,78,1000,5340)

// 交换法排序
function ExchangeSort($arr){
   $num = count($arr);
   for($i=0;$i<$num-1;$i++){
      for($j=$i+1;$j<$num;$j++){
          if($arr[$j]<$arr[$i]){
	   		$iTemp = $arr[$i];
			$arr[$i] = $arr[$j];
			$arr[$j] = $iTemp;
          }
      }
   }
   return $arr;
}

$array=array(1,3,6,2,4,8,5340,33,45,78);
print_r(ExchangeSort($array));//Array ( 1 ,2 ,3 ,4 ,6 ,8 ,33,45,78,1000,5340
```

顶部

PHP算法

目录

相关推荐