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]
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中文網。
相關推薦:
#以上是關於冒泡,二分法插入,快速排序演算法的介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章!