Rumah > Artikel > pembangunan bahagian belakang > 关于冒泡,二分法插入,快速排序算法的介绍
1.冒泡排序算法
过程:
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; } ?>
3.快速排序
过程:
1. 在数组中找一个元素作为key,一般取数组第一个元素作为key
2. i=0, j=数组长度-1
3. j-- 当 arr[j]6f0d6aabda0f13034815fa6a60224234key, arr[i]与arr[j]交换位置
5. 重复3,4 直到 i==j 时,完成。
6. 将key分隔的左右两组元素再分别执行 1,2,3,4,5 (递归)。
<?php // 快速排序 $arr = createarr(20); printarr($arr); quicksort($arr, 0, count($arr)-1); 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 quicksort(&$arr, $low, $high){ if($low>=$high){ return ; } $key = $arr[$low]; $i = $low; $j = $high; $flag = 1; while($i!=$j){ switch($flag){ case 0: if($arr[$i]>$key){ $tmp = $arr[$i]; $arr[$i] = $arr[$j]; $arr[$j] = $tmp; $flag = 1; }else{ $i++; } break; case 1: if($arr[$j]<$key){ $tmp = $arr[$i]; $arr[$i] = $arr[$j]; $arr[$j] = $tmp; $flag = 0; }else{ $j--; } break; } } quicksort($arr, $low, $i-1); quicksort($arr, $i+1, $high); } ?>
本篇文章讲解了于冒泡,二分法插入,快速排序算法,更多相关内容请关注php中文网。
相关推荐:
Atas ialah kandungan terperinci 关于冒泡,二分法插入,快速排序算法的介绍. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!