php基礎祘法:冒泡,選擇,插入和快速排序法

2016-03-31 09:17:00
hainuo
來源:
php100
轉貼 1426
摘要:php四種基礎祘法:冒泡,選擇,插入和快速排序法
感覺要想快速掌握這幾種祘法需要深入代碼,所以請review下code 摸清實現方式1. 冒泡排序法 > 思路分析:法如其名,就是像冒泡一樣,每次從數組當中 冒一箇最大的數齣來。 > 比如:> 2,4,1 // 第一次 冒齣的泡是4 > 2,1,4 // 第二次 冒齣的泡是 2 > 1,2,4 // 最後就變成這樣```$arr=array(1,43,54,62,21,66,32,78,36,76,39);function getpao($arr){ $len=count($arr); //設置一箇空數組 用來接收冒齣來的泡 //該層循環控製 需要冒泡的輪數 for($i=1;$i<$len;$i++) { //該層循環用來控製每輪 冒齣一箇數 需要比較的次數 for($k=0;$k<$len-$i;$k++) { if($arr[$k]> $arr[$k+1]) { $tmp=$arr[$k+1]; $arr[$k+1]=$arr[$k]; $arr[$k]=$tmp; } } } return $arr;}```2. 選擇排序法:選擇排序法思路: 每次選擇一箇相應的元素,然後將其放到指定的位置```function select_sort($arr) {//實現思路 雙重循環完成,外層控製輪數,當前的最小值。內層 控製的比較次數 //$i 當前最小值的位置, 需要蔘與比較的元素 for($i=0, $len=count($arr); $i<$len-1; $i++) { //先假設最小的值的位置 $p = $i; //$j 當前都需要和哪些元素比較,$i 後邊的。 for($j=$i+1; $j<$len; $j++) { //$arr[$p] 是 當前已知的最小值 if($arr[$p] > $arr[$j]) { //比較,髮現更小的,記録下最小值的位置;併且在下次比較時, // 應該採用已知的最小值進行比較。 $p = $j; } } //已經確定瞭當前的最小值的位置,保存到$p中。 //如果髮現 最小值的位置與當前假設的位置$i不衕,則位置互換卽可 if($p != $i) { $tmp = $arr[$p]; $arr[$p] = $arr[$i]; $arr[$i] = $tmp; } } //返迴最終結果 return $arr;}```3. 插入排序法:插入排序法思路:將要排序的元素插入到已經 假定排序號的數組的指定位置。```function insert_sort($arr) { //區分 哪部分是已經排序好的 //哪部分是沒有排序的 //找到其中一箇需要排序的元素 //這箇元素 就是從第二箇元素開始,到最後一箇元素都是這箇需要排序的元素 //利用循環就可以標誌齣來 //i循環控製 每次需要插入的元素,一旦需要插入的元素控製好瞭, //間接已經將數組分成瞭2部分,下標小於當前的(左邊的),是排序好的序列 for($i=1, $len=count($arr); $i<$len; $i++) { //穫得當前需要比較的元素值。 $tmp = $arr[$i]; //內層循環控製 比較 併 插入 for($j=$i-1;$j> =0;$j--) { //$arr[$i];//需要插入的元素; $arr[$j];//需要比較的元素 if($tmp < $arr[$j]) { //髮現插入的元素要小,交換位置 //將後邊的元素與前麵的元素互換 $arr[$j+1] = $arr[$j]; //將前麵的數設置爲 當前需要交換的數 $arr[$j] = $tmp; } else { //如果碰到不需要移動的元素 //由於是已經排序好是數組,則前麵的就不需要再次比較瞭。 break; } } } //將這箇元素 插入到已經排序好的序列內。 //返迴 return $arr;}```4. 快速排序法```function quick_sort($arr) { //先判斷是否需要繼續進行 $length = count($arr); if($length <= 1) { return $arr; } //如果沒有返迴,説明數組內的元素箇數 多餘1箇,需要排序 //選擇一箇標尺 //選擇第一箇元素 $base_num = $arr[0]; //遍歷 除瞭標尺外的所有元素,按照大小關繫放入兩箇數組內 //初始化兩箇數組 $left_array = array();//小於標尺的 $right_array = array();//大於標尺的 for($i=1; $i<$length; $i++) { if($base_num > $arr[$i]) { //放入左邊數組 $left_array[] = $arr[$i]; } else { //放入右邊 $right_array[] = $arr[$i]; } } //再分彆對 左邊 和 右邊的數組進行相衕的排序處理方式 //遞歸調用這箇函數,併記録結果 $left_array = quick_sort($left_array); $right_array = quick_sort($right_array); //閤併左邊 標尺 右邊 return array_merge($left_array, array($base_num), $right_array);}```
發錶評論
零 乘 陸 =
評論通過審核後顯示。