PHP学习 -- 数组排序算法

本文涉及到 冒泡算法 选择排序 快速排序 归并排序 顺序查找 二分/折半查找

<?php

// 数组排序算法

// 冒泡算法 两个数字比较 较大的数字放到右边

$arr = array(9,5,6,1,89,6,6,1,2,3,6);

for($j = 0,$len = count($arr);$j < $len;$j++){

for($i =0,$len =count($arr);$i < $len-1-$j;$i++){

if($arr[$i] > $arr[$i+1]){

$temp = $arr[$i];

$arr[$i] = $arr[$i+1];

$arr[$i+1] = $temp;

}

}

}

echo '<pre>';

print_r($arr);

echo '<hr>';

// 选择排序

$arr1 = array(5,6,2,3,1,0);

for($i = 0,$len = count($arr1);$i < $len;$i++){

// 假定一个最小的

$min = $i;

// 用假定最小的和剩余其他的比较

for($j = $i+1;$j < $len;$j++){

// 当前比较的元素 < 假定的，把当前的下标赋值给min

if($arr1[$j] < $arr1[$min]){

$min = $j;

}

}

// 交换真正的最小值

if($min != $i){

$temp = $arr1[$i];

$arr1[$i] = $arr1[$min];

$arr1[$min] = $temp;

}

}

echo '<pre>';

print_r($arr);

echo '<hr>';

// 快速排序

$arr2 = [5,6,1,2,3,0];

function quick_sort($arr2){

// 递归出口 数组长度<=1时候就已经排好了

$len = count($arr2);

if($len <=1) return $arr2;

// 存放数组

$left = $right = array();

for($i =1;$i < $len;$i++){

// 一般情况下把第一个元素当作比较元素，比它小的放到left里面，大的放到right里面

if($arr2[$i] < $arr2[0]){

$left[] = $arr2[$i];

}else{

$right[] = $arr2[$i];

}

}

// 递归点

$left = quick_sort($left);

$right = quick_sort($right);

returnarray_merge($left,array($arr2[0]),$right);

}

echo '<pre>';

print_r(quick_sort($arr2));

echo '<hr>';

// 归并排序

// 二路归并 必须是两个有序数组

// $arr4 = [1,3,5];

// $arr5 = [2,3];

// // 创建一个空数组用于存放归并空间

// $arr6 = array();

// while (count($arr4) && count($arr5)) {

// $arr6[] = $arr4[0] < $arr5[0] ? array_shift($arr4) : array_shift($arr5);

// }

// print_r(array_merge($arr6,$arr4,$arr5));

$arr3 = [5,1,3,9,0];

function merge_sort($arr){

// 递归出口 数组长度<=1时候就已经排好了

$len = count($arr);

if($len <=1) return $arr;

// 拆分

$middle = floor($len/2);

$left = array_slice($arr,0,$middle);

$right = array_slice($arr,$middle);

// 递归点，保证left和right为有序数组

$left = merge_sort($left);

$right = merge_sort($right);

$m = array();

while (count($left) &&count($right)) {

// 只要left right里面有元素，就进入循环

// 取出left right里面的第一个元素进行比较 哪个小就把小的放入m中

$m[] = $left[0] < $right[0] ? array_shift($left) : array_shift($right);

}

return (array_merge($m,$left,$right));

}

print_r(merge_sort($arr3));

echo '<hr>';

// 查找算法

// 顺序查找

$arr4 = [8,9,7,12,0];

functioncheck_order($arr,$num){

for($i =0,$len =count($arr);$i < $len;$i++){

if($arr[$i] == $num){

return $i;

}

}

returnfalse;

}

var_dump(check_order($arr4,102));

// 二分/折半 查找

$arr5 = [1,5,7,15,98,120];

$ress = 5;

functioncheck_break($arr,$ress){

// 取得边界

$right = count($arr);

$left = 0;

while ($left <= $right) {

// 得到中间值

$middle = floor(($left + $right)/2);

// 匹配数据

if($arr[$middle] == $ress){

return $middle +1;

}

// 值在右边

if($arr[$middle] < $ress){

$left = $middle + 1;

}else{

$right = $middle - 1;

}

}

returnfalse;

}

var_dump(check_break($arr5,$ress));