[TOC] ## 排序算法 冒泡排序、直接插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序 ### **冒泡排序** * 兩兩相鄰的數進行比較，反序則交換 * 時間復雜度：最壞O(n^2) ， 平均O(n^2) * 空間復雜度：O(1) ``` $arr = [3,8,1,5,2]; for($i = 0; $i < count($arr); $i++ ){ for($j = $i+1; $j < count($arr); $j++ ){ if($arr[$i] > $arr[$j]){ $temp = $arr[$i]; $arr[$i] = $arr[$j]; $arr[$j] = $temp; } } } ``` ### **直接插入排序** * 每次從無序表中取出第一個元素，插入到有序表中 * 時間復雜度：最壞O(n^2) ， 平均O(n^2) * 空間復雜度：O(1) ``` /** * 分成有序表和無序表 * 第一位為有序組，在左側，其余則是無序組 * 剩下的依次和左側進行比對插入 */ $arr = array(1,3,6,4,1,2); $count = count($arr); for($i = 1; $i < $count; $i++){ $temp = $arr[$i]; // 需要比較的值 for($j = $i-1; $j >= 0; $j--){ if($arr[$j] > $temp){ $arr[$j+1] = $arr[$j]; $arr[$j] = $temp; }else{ break; } } } ``` ### **希爾排序** * 按下標的一定增量分組，對每一組使用`直接插入排序`隨著增量逐漸減少，每組包含的關鍵字越來越多，當增量減少至 1 時，整個序列恰好被分成一組，算法便終止。 * 時間復雜度：最壞O(n^2) ， 平均O(n*long2n) * 空間復雜度：O(1) ``` $arr = array(49,38,65,97,76,13,27,49,55,04); $count = count($arr); $inc = $count; //增量 do { //計算增量 $inc = ceil($inc / 2); for ($i = $inc; $i < $count; $i++) { $temp = $arr[$i]; //設置哨兵 //需將$temp插入有序增量子表 for ($j = $i - $inc; $j >= 0 && $arr[$j + $inc] < $arr[$j]; $j -= $inc) { $arr[$j + $inc] = $arr[$j]; //記錄后移 } //插入 $arr[$j + $inc] = $temp; } //增量為1時停止循環 } while ($inc > 1); ``` ### **選擇排序** * 每次從數據中選擇最小或最大的一個元素，放到序列的起始位置 * 時間復雜度：最壞O(n^2) ， 平均O(n^2) * 空間復雜度：O(1) ``` $arr = array(1,3,6,4,1,2); for ($i = 0; $i < count($arr); $i++) { $p = $i; //假設為最小 for ($k = $i+1; $k < count($arr); $k++) { if($arr[$p] < $arr[$k]){ //比對最小值 $p = $k; } } if($p != $i){ //位置不相等，進行替換 $tmp = $arr[$p]; $arr[$p] = $arr[$i]; $arr[$i] = $tmp; } } var_dump($arr);die; ``` ### **快速排序** * 通過一趟排序分成一大一小兩組，然后分別對兩組進行同樣的排序，用遞歸完成 * 時間復雜度：最壞O(n^2) ， 平均O(nlong2n) * 空間復雜度：最差O(n)，平均O(log2n) ### **堆排序** * 按照大小在二叉樹位置上排列，滿足父節點大于等于子節點。如果根節點是最大的數叫大根堆，最小就叫小根堆 * 時間復雜度：最壞O(nlog2n) ， 平均O(nlong2n) * 空間復雜度：最差O(1) ### **歸并排序** * 將兩個或以上的有序表合并成一個新的有序表。 * 時間復雜度：最壞O(nlog2n) ， 平均O(nlong2n) * 空間復雜度：最差O(n) ## 查找算法 二分查找、順序查找 ### **二分查找** * 從數組中間的元素開始，如果中間元素正好是查找的元素，搜索結束，如果大于或小于中間元素則在數組大于或者小于中間元素的那一半查找，直到找到或為空。 * 時間復雜度：最壞O(log2n) ， 平均O(long2n) * 空間復雜度：迭代O(1)、遞歸O(long2n) ### **順序查找** * 按一定的順序檢查數組中每一個元素，直到找到為止。 * 時間復雜度：最壞O(n) ， 平均O(n) * 空間復雜度：O(1)