- 冒泡
$arr = array(3,44,38,5,47,15,36,26,27,2,46,4,19,50,48);
$arr = array(2,3,4,5,15,19,26,27,36,38,44,46,47,48,50);
$times = 0;//记录比较的次数
$len=count($arr);
//控制需要冒泡的轮数
for($i=1;$i<$len;$i++){
$swapped = false;//[优化]跳出循环之用
//控制每轮 冒出一个数 需要比较的次数
for($k=0;$k<$len-$i;$k++){
$times += 1;
if($arr[$k]>$arr[$k+1]){
$tmp=$arr[$k+1];
$arr[$k+1]=$arr[$k];
$arr[$k]=$tmp;
$swapped = true;
}
}
$times += 1;
if(!$swapped)
break;
}
echo $times;print_r($arr);
冒泡排序无论代码怎么实现，交换的次数是同样。不同的是，设计良好的算法对于排序良好的输入，进行比较的次数会骤减。
- 插入排序
function insert_sort(&$arr){
$sum = count($arr);
for($i=1;$i<$sum;$i++){
$tmp=$arr[$i];
$key=$i-1;
while($key>=0 && $tmp<$arr[$key]){
$arr[$key+1]=$arr[$key];
$key--;
}
$key != $i-1 && $arr[$key+1] = $tmp;//如果有移动，就插入
}
}
- 希尔排序
function shell_sort(&$arr)
{
if(!is_array($arr)) return;
$n = count($arr);
for($gap=floor($n/2);$gap>0;$gap=floor($gap/=2))
{
for($i=$gap;$i<$n;++$i)
{
for($j=$i-$gap;$j>=0 && $arr[$j+$gap]<$arr[$j];$j-=$gap)
{
$temp = $arr[$j];
$arr[$j] = $arr[$j+$gap];
$arr[$j+$gap] = $temp;
}
}
}
}
- 选择排序
function selection_sort(&$array){
$count=count($array);
for($i=0;$i<$count-1;$i++){
/*findtheminest*/
$min=$i;
echo'$min-->'.$array[$min].'-->';
for($j=$i+1;$j<$count;$j++){
//由小到大排列
if($array[$min]>$array[$j]){
//表明当前最小的还比当前的元素大
$min=$j;
//赋值新的最小的
}
}
echo$array[$min].'coco<br/>';
/*swap$array[$i]and$array[$min]即将当前内循环的最小元素放在$i位置上*/
if($min!=$i){
$temp=$array[$min];
$array[$min]=$array[$i];
$array[$i]=$temp;
}
}
}
- 快速排序
function quickSort($arr){
if(count($arr)>1){
$k=$arr[0];
$x=array();
$y=array();
$size=count($arr);
for($i=1;$i<$size;$i++){
if($arr[$i]<=$k){
$x[]=$arr[$i];
}elseif($arr[$i]>$k){
$y[]=$arr[$i];
}
}
$x = quickSort($x);
$y = quickSort($y);
return array_merge($x,array($k),$y);
}else{
return $arr;
}
}
- 选择排序
function selectSort(&$arr){
$n = count($arr);
for($i=0; $i<$n-1; $i++){
$min_k = $i;
$min_v = $arr[$i];
for($j = $i+1; $j<$n; $j++){
if($arr[$j] < $min_v){
$min_v = $arr[$j];
$min_k = $j;
}
}
$arr[$min_k] = $arr[$i];
$arr[$i] = $min_v;
}
}
