冒泡、二分法插入及快速排序算法

冒泡、二分法插入及快速排序算法2015-10-221.冒泡排序算法

过程：

1.遍历整个数组，每两两相邻的元素进行比较，如$a[$i]>$a[$i+1]则互换位置，每次比较消除一个逆序。

2.每一次循环后，下次再需要循环的次数减少1。

<？php// 冒泡排序$arr = createarr（20）;printarr（$arr）;popsort（$arr）;printarr（$arr）;function createarr（$num=10）{$arr = array（）;for（$i=0; $i<$num; $i++）{array_push（$arr, mt_rand（0,999））;}return $arr;}function printarr（$arr）{echo "arr:".implode（",", $arr）."<br>";}function popsort（&$arr）{for（$i=0,$length=count（$arr）-1; $i<$length; $i++）{for（$j=0; $j<$length-$i; $j++）{if（$arr[$j]>$arr[$j+1]）{$tmp = $arr[$j];$arr[$j] = $arr[$j+1];$arr[$j+1] = $tmp;}}}}？>

2.二分法插入排序

过程:

1.首先，原数组是一个有序序列，$low=0 $high=count（$arr）-1。

2.将要插入的数与数组中间位置的元素进行比较，

如果比中间元素大，则$low=$mid+1作为下一次判断的数组开头。

如果比中间元素小，则$high=$mid-1作为下一次判断的数组结尾。

3.直到$low>$high结束，$low就是新元素插入的位置。

4.将数组中从$low开始的元素全部向后移动一位，之后在$low位置插入新元素。

<？php// 二分法插入排序$arr = createarr（20）;$key = mt_rand（0,99）;printarr（$arr）;echo "key=".$key."<br>";binsort（$arr, $key）;printarr（$arr）;function createarr（$num=10）{$arr = array（）;for（$i=0; $i<$num; $i++）{array_push（$arr, mt_rand（0,99））;}sort（$arr）; // 有序序列return $arr;}function printarr（$arr）{echo "arr:".implode（",", $arr）."<br>";}function binsort（&$arr, $key）{$low = 0;$high = count（$arr）-1;while（$low<=$high）{$m = $low + （int）（（$high-$low）/2）;$mkey = $arr[$m];if（$key>=$mkey）{$low = $m + 1;}else{$high = $m - 1;}}// 移动插入位置之后的元素,插入新元素for（$i=count（$arr）-1; $i>=$low; $i--）{$arr[$i+1] = $arr[$i];}$arr[$low] = $key;}？>