以前说起写算法，基本上都是拿C语言来写，因为用C可以更清楚的理解各种排序算法和数据结构。今天遍换成使用PHP语言来写几个常用的算法。
这次要写的算法包括：

  • 冒泡排序
  • 插入排序
  • 选择排序（直接）
  • 快速排序
  • 二分查找

冒泡：

<?php
$arr = array(4,3,5,6,8,0,10,15,11);
echo implode(' ',$arr);
//冒泡排序 最坏 平均O(N^2) 最好O(N)
function BubbleSort($arr){
	$length = count($arr);
	if($length <= 1){
		return $arr;
	}
	for($i=0;$i<$length;$i++){
		for($j=0;$j<$length-$i-1;$j++){
			if($arr[$j] > $arr[$j+1]){
				$tmp = $arr[$j];
				$arr[$j] = $arr[$j+1];
				$arr[$j+1] = $tmp;
			}
		}
	}
	return $arr;
}
echo "\nBubbleSort:\n";
echo implode(' ',BubbleSort($arr))."\n";
?>

插入：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
<?php
header("Content-type:text/html;charset=utf-8");
$arr = array(4,3,5,6,8,0,10,15,11);
echo implode(' ',$arr);
//插入排序  最坏情况下O(N^2)   最好情况下O(N)
function InsertSort($arr){
	$length = count($arr);
	if($length <= 1){
		return $arr;
	}
	for($i=1;$i<$length;$i++){
		$now = $arr[$i];
		$j = $i-1;
		while ($now < $arr[$j] && $j >= 0) {
			$arr[$j] = $arr[$j--];
		}
		$arr[++$j] = $now;
	}
	return $arr;
}
echo "\nInsertSort:\n";
echo implode(' ',InsertSort($arr))."\n";

直接选择：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
<?php
header("Content-type:text/html;charset=utf-8");
$arr = array(4,3,5,6,8,0,10,15,11);
echo implode(' ',$arr);
//选择排序 最坏 最好 平均都是O(N^2)
function SelectSort($arr){
	$length = count($arr);
	if($length <= 1){
		return $arr;
	}
	for($i=0;$i<$length;$i++){
		$min = $i;
		for($j=$i+1;$j<$length;$j++){
			if($arr[$min]>$arr[$j]){
				$min = $j;
			}
		}
		if($min != $i){
			$tmp = $arr[$min];
			$arr[$min] = $arr[$i];
			$arr[$i] = $tmp;
		}
	}
	return $arr;
}
echo "\nSelectSort:\n";
echo implode(' ',SelectSort($arr))."\n";

快排:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
<?php
header("Content-type:text/html;charset=utf-8");
$arr = array(4,3,5,6,8,0,10,15,11);
echo implode(' ',$arr);
//快速排序 最好 平均O(NlgN) 最坏O(N^2)
function QuickSort($arr){
	$length = count($arr);
	if($length <= 1){
		return $arr;
	}
	$middle = $arr[0];
	$leftArray = array();
	$rightArray = array();
	for($i=1;$i<$length;$i++){
		if($arr[$i]<$middle){
			array_push($leftArray,$arr[$i]);
			// $leftArray[] = $arr[$i];
		}else{
			array_push($rightArray,$arr[$i]);
			// $rightArray[] = $arr[$i];
		}
	}
	$leftArray = QuickSort($leftArray);
	$rightArray = QuickSort($rightArray);
	return array_merge($leftArray,array($middle),$rightArray);
}
echo "\nQuickSort:\n";
echo implode(' ',QuickSort($arr))."\n";

还有一个，排好序的数组，进行查找key的位置：

二分查找：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<?php
header("Content-type:text/html;charset=utf-8");
$arr = array(0,1,2,3,4,5,6,7,8,9,10);
echo implode(' ',$arr);
//二分查找  
function BinarySearch($arr,$low,$hight,$key){
	while ($low <= $hight) {
		$mid = intval(($low+$hight)/2);
		if($key == $arr[$mid]){
			return $mid;
		}else if($key < $arr[$mid]){
			$hight = $mid - 1;
		}else{
			$low = $mid + 1;
		}
	}
	return -1;
}
$key = 4;
echo "\nBinarySearch:{$key}\n";
echo BinarySearch($arr,0,count($arr)-1,$key)."\n";