排序 · PHP筆記

[排序](https://www.cnblogs.com/lichihua/diary/2018/08/16/9484909.html) 1\. 冒泡排序? 思路分析：在要排序的一組數中，對當前還未排好的序列，從前往后對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即，每當兩相鄰的數比較后發現它們的排序與排序要求相反時，就將它們互換。? 代碼實現： ~~~ /** * 冒泡排序 * @param array $arr * @return array */ function bubbleSort($arr) { // 數組長度 $length = count($arr); // 正向遍歷數組 for ($i = 1; $i < $length; $i++) { // 反向遍歷 for ($j = $length - 1; $j >= $i ; $j--) { // 相鄰兩個數比較 if ($arr[$j] < $arr[$j-1]) { // 暫存較小的數 $iTemp = $arr[$j-1]; // 較大的放前面 $arr[$j-1] = $arr[$j]; // 較小的放后面 $arr[$j] = $iTemp; } } } return $arr; } ~~~ 2.選擇排序思路分析：在要排序的一組數中，選出最小的一個數與第一個位置的數交換。然后在剩下的數當中再找最小的與第二個位置的數交換，如此循環到倒數第二個數和最后一個數比較為止。? 代碼實現： ~~~ function xsort($arr){ $length=count($arr); for ($i=0; $i <$length-1 ; $i++) { for ($k=$i+1; $k <$length ; $k++) { //當前值arr[$i]與余下的比較 if ($arr[$i]>$arr[$k]) { $temp=$arr[$k]; $arr[$k]=$arr[$i]; $arr[$i]=$temp; } } } return $arr; } /** * 選擇法排序 * @param array $arr * @return array */ function choiceSort($arr) { // 數組長度 $length = count($arr); // 遍歷數組 for ($i = 0;$i < $length-1; $i++) { // 暫存當前值 $iTemp = $arr[$i]; // 暫存當前位置 $iPos = $i; // 遍歷當前位置以后的數據 for ($j = $i + 1;$j < $length; $j++){ // 如果有小于當前值的 if ($arr[$j] < $iTemp) { // 暫存最小值 $iTemp = $arr[$j]; // 暫存位置 $iPos = $j; } } // 把當前值放到算好的位置 $arr[$iPos] = $arr[$i]; // 把當前值換成算好的值 $arr[$i] = $iTemp; } return $arr; } ~~~ 3.插入排序思路分析：在要排序的一組數中，假設前面的數已經是排好順序的，現在要把第n個數插到前面的有序數中，使得這n個數也是排好順序的。如此反復循環，直到全部排好順序。? 代碼實現： ~~~ /** * 插入法排序 * @param array $arr * @return array */ function insertSort($arr){ $length = count($arr); // 遍歷數組 for ($i = 1;$i < $length; $i++) { // 獲得當前值 $iTemp = $arr[$i]; // 獲得當前值的前一個位置 $iPos = $i - 1; // 如果當前值小于前一個值切未到數組開始位置 while (($iPos >= 0) && ($iTemp < $arr[$iPos])) { // 把前一個的值往后放一位 $arr[$iPos + 1] = $arr[$iPos]; // 位置遞減 $iPos--; } $arr[$iPos+1] = $iTemp; } return $arr; } ~~~ 4.快速排序思路分析：選擇一個基準元素，通常選擇第一個元素或者最后一個元素。通過一趟掃描，將待排序列分成兩部分，一部分比基準元素小，一部分大于等于基準元素。此時基準元素在其排好序后的正確位置，然后再用同樣的方法遞歸地排序劃分的兩部分。? 代碼實現： ~~~ /** * 快速排序 * @param array $arr * @return array */ function quickSort($arr){ $length = count($arr); $l = $r = 0; $left = $right = array(); // 從索引的第二個開始遍歷數組 for ($i = 1;$i < $length; $i++) { // 如果值小于索引1 if ($arr[$i] < $arr[0]) { // 裝入左索引數組(小于索引1的數據) $left[] = $arr[$i]; $l++; } else { // 否則裝入右索引中(大于索引1的數據) $right[] = $arr[$i]; $r++; // } } // 如果左索引有值則對左索引排序 if($l > 1) { $left = QuickSort($left); } // 排序后的數組 $new_arr = $left; // 將當前數組第一個放到最后 $new_arr[] = $arr[0]; // 如果又索引有值則對右索引排序 if ($r > 1) { $right = QuickSort($right); } // 根據右索引的長度再次增加數據 for($i = 0;$i < $r; $i++) { $new_arr[] = $right[$i]; } return $new_arr; } ~~~ 5.希爾排序思路分析：將數組按指定步長分隔成若干子序列，然后分別對子序列進行排序（在這是直接）? 代碼實現： ~~~ /** * 希爾排序 * @param array $arr * @return array */ function shellSort($arr) { $len = count($arr); $k = floor($len/2); while($k > 0) { for($i = 0; $i < $k; $i++) { for($j = $i; $j < $len, ($j + $k) < $len; $j = $j + $k) { if($arr[$j] > $arr[$j+$k]) { $tmp = $arr[$j+$k]; $arr[$j+$k] = $arr[$j]; $arr[$j] = $tmp; } } } $k = floor($k/2); } return $arr; } ~~~ 6.堆排序思路分析：調整子堆的為大根堆的過程? 代碼實現： ~~~ /** * 堆排序 * @param array &$arr 數組 * @param int $s 子堆的根的位置 * @param int $m 堆最后一個元素位置 * @return array */ function heapAdjust(&$arr, $s, $m) { $tmp = $arr[$s]; // 在調整為大根堆的過程中可能會影響左子堆或右子堆 // for循環的作用是要保證子堆也是大根堆 for($j = 2*$s + 1; $j <= $m; $j = 2*$j + 1) { // 找到根節點的左右孩子中的最大者，然后用這個最大者與根節點比較， // 若大則進行調整，否則符合大根堆的特點跳出循環 if($j < $m && $arr[$j] < $arr[$j+1]) { $j++; } if($tmp >= $arr[$j] ) { break; } $arr[$s] = $arr[$j]; $s = $j; } $arr[$s] = $tmp; } /** * 堆排序 * @param array $arr 數組 * @return array */ function heapSort($arr) { $len = count($arr); // 依次從子堆開始調整堆為大根堆 for($i = floor($len/2-1); $i >= 0; $i--) { heapAdjust($arr, $i, $len-1); } // 依次把根節點調換至最后一個位置，再次調整堆為大根堆，找到次最大值， // 依次類推得到一個有序數組 for($n = $len-1; $n > 0; $n--) { $tmp = $arr[$n]; $arr[$n] = $arr[0]; $arr[0] = $tmp; heapAdjust($arr, 0, $n-1); } return $arr; } ~~~ 7.歸并排序思路分析：這里實現的是兩路歸并(分別將有序的arr1\[s..m\]、arr1\[s..m\]、arr2\[m+1..n\]歸并為有序的$arr2\[s..n\])? 代碼實現： ~~~ /** * 歸并排序 * @param array &$arr1 * @param array &$arr2 * @param int $s * @param int $m * @param int $n */ function Merge(&$arr1, &$arr2, $s, $m, $n) { for($k = $s,$i = $s, $j = $m+1; $i <= $m && $j <= $n; $k++) { if($arr1[$i]<$arr1[$j]) { $arr2[$k] = $arr1[$i++]; }else { $arr2[$k] = $arr1[$j++]; } } if($i <= $m) { for(; $i <= $m; $i++) { $arr2[$k++] = $arr1[$i]; } }else if($j <= $n) { for(; $j <= $n; $j++) { $arr2[$k++] = $arr1[$j]; } } } /** * 遞歸形式的兩路歸并 * @param array &$arr1 * @param array &$arr2 * @param int $s * @param int $t */ function MSort(&$arr1, &$arr2, $s, $t) { if($s == $t) { $arr2[$s] = $arr1[$s]; }else { $m = floor(($s+$t)/2); $tmp_arr = array(); MSort($arr1, $tmp_arr, $s, $m); MSort($arr1, $tmp_arr, $m+1, $t); Merge($tmp_arr, $arr2, $s, $m, $t); } } /** * 對一位數組$arr[0..n-1]中的元素進行兩路歸并 * @param array $arr * @return array */ function mergeSort($arr) { $len = count($arr); MSort($arr, $arr, 0, $len-1); return $arr; } ~~~ 8.交換法排序代碼實現： ~~~ /** * 交換法排序 * @param array $arr * @return array */ function swapSort($arr){ $length = count($arr); // 遍歷數組 for ($i = 0;$i < $length - 1; $i++) { // 獲得當前索引的下一個索引 for ($j = $i + 1; $j < $length; $j++) { // 比較相鄰兩個的值大小 if ($arr[$j] < $arr[$i]) { // 暫存較小的數 $iTemp = $arr[$i]; // 較大的放前面 $arr[$i] = $arr[$j]; // 較小的放后面 $arr[$j] = $iTemp; } } } return $arr; } ~~~