[TOC] :-:  # 冒泡排序 冒泡排序又稱為泡式排序，是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤則交換兩個元素，走訪數列的工作是重復的進行直到沒有需要交換的，也就是說該數列已經排序完成，這個算法名字的由來是因為**越小的元素會經由交換慢慢"浮"到數列的頂端**。 1. 從頭開始比較兩個元素,如果順序錯誤則交換兩個元素，循環比較數組直到沒有需要交換的 2. 1和2、2和3… 2 3. 里面的循環執行完第一輪，最末尾的元素就是最大的元素，外層循環走完，數組也算排序完成 ~~~php function bubbleSort($arr) { $count = count($arr); for ($i = 0; $i < $count- 1; $i++) { for ($j = 0; $j < $count - $i -1; $j++) { if ($arr[$j] < $arr[$j + 1]) { $tmp = $arr[$j]; $arr[$j] = $arr[$j + 1]; $arr[$j + 1] = $tmp; } } } return $arr; } ~~~ # 快速排序 快速排序，又稱分區交換排序，簡稱快排，它采用了一種分治的策略，通常稱其為分治法，把一個序列分為較小和較大的2個子序列，然后遞歸的排序兩個子系列。 1. 從數列中挑出一個數作為**基準元素(pivot)**。通常選擇第一個或最后一個元素。 2. 掃描數列，**以基準元素為比較對象，把數列分成兩個區**。規則是：小的移動到基準元素前面，大的移到后面，相等的前后都可以。分區完成之后，基準元素就處于數列的中間位置。 3. 然后再用同樣的方法，**遞歸地排序劃分的兩部分**。 ~~~php function quickSort($arr) { $count = count($arr); //先設定結束條件，判斷是否需要繼續進行 if ($count <= 1) { return $arr; } //選擇第一個元素作為基準元素 $pivot = $arr[0]; //初始化左右數組,左小右大 $left_arr = $right_arr = array(); //遍歷除基準元素外的所有元素，按照大小關系放入左右數組內 for($i = 1; $i < $count; $i++) { if ($arr[$i] < $pivot) { $left_arr[] = $arr[$i]; } else { $right_arr[] = $arr[$i]; } } //再分別對左右數組進行相同的排序 $left = quickSort($left_arr); $right = quickSort($right_arr); return array_merge($left, array($pivot), $right); } ~~~ # 插入排序 插入排序是一種簡單直觀的排序算法。 插入排序的工作原理是：**將需要排序的數，與前面已經排好序的數據從后往前進行比較，使其插入到相應的位置。** 插入排序在實現上，通常采用in-place排序，即只需用到O(1)的額外空間的排序。 因而，在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。 1. 從第一個元素開始，該元素可以認為已經被排序； 2. 取出下一個元素，在已經排序的元素序列中從后向前掃描； 3. 如果以排序的元素大于新元素，將該元素移到下一位置； 4. 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置； 5. 將新元素插入到該位置中； 6. 重復步驟2。 ~~~php funciton insertSort($arr) { for ($i = 1; $i < count($arr); $i++) { $tmp = $arr[$i]; for ($j = $i - 1; $j >=0; $j--) { if ($tmp < $arr[$j]) { $arr[$j + 1] = $arr[$j]; $arr[$j] = $tmp; } else { break; } } } return $arr; } ~~~ # 選擇排序 選擇排序是一種簡單直觀的排序算法。首先在未排序序列中找到最大（小）元素，存放到排序序列的起始位置，然后在從剩余的未排序的元素中據需尋找最大（小）元素，然后放到已排序的序列的末尾，一次類推，知道所有元素均排序完畢。 1. 首先，在序列中找到最小元素，存放到排序序列的起始位置； 2. 接著，從剩余未排序元素中繼續尋找最小元素，放到已排序序列的末尾。 3. 重復第二步，直到所有元素均排序完畢。 ~~~php function selectSort($arr) { $count = count($arr); for ($i = 0; $i < $count; $i++) { $p = $i; for ($j = $i + 1; $j < $count; $j ++) { if ($arr[$p] > $arr[$j]) { $p = $j; } } $tmp = $arr[$p]; $arr[$p] = $arr[$i]; $arr[$i] = $tmp; } return $arr; } ~~~ # 歸并排序 歸并排序是建立在歸并操作上的一種有效的排序算法。 歸并排序將待排序的序列分成若干組，保證每組都有序，然后再進行合并排序，最終使整個序列有序。 該算法是采用分治法的一個非常典型的應用。 1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列； 2. 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置 3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置 4. 重復步驟3直到某一指針達到序列尾 5. 將另一序列剩下的所有元素直接復制到合并序列尾 ~~~php function mergeSort($arr) { $count = count($arr); if ($count <= 1) { return $arr; } $left = merge_sort(array_slice($arr, 0, floor($n / 2))); $right = merge_sort(array_slice($arr, 0, floor($n / 2))); $arr = merge($left, $right); return $arr; } function merge($left, $right) { $arr = []; $i = $j = 0; while ($i < count($left) && $j < count($right)) { if ($left[$i] < $right[$j]) { $arr[] = $left[$i]; $i++; } else { $arr[] = $right[$j]; $j++; } $arr = array_merge($arr, array_slice($left, $i)); $arr = array_merge($arr, array_slice($right, $j)); return $arr; } } ~~~ # 希爾排序 希爾排序，也稱**遞減增量**排序算法，是插入排序的一種更高效的改進版本。 但希爾排序是非穩定排序算法 希爾排序是基于插入排序的以下兩點性質而提出改進方法的： * 插入排序在對幾乎已經排好序的數據操作時， 效率高， 即可以達到線性排序的效率 * 但插入排序一般來說是低效的， 因為插入排序每次只能將數據移動一位 1. 先將整個待排序的記錄序列分割成為若干子序列，分別進行直接插入排序 2. 待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。 ~~~php function shellSort($arr) { $count = count($arr); $step = 2; $gap = intval($count / $step); while ($gap > 0) { for ($gi = 0; $gi < $gap; $gi++) { for ($i = $gi; $i < $count; $i += $gap) { $key = $arr[$i]; for ($j = $i - $gap; $j >= 0 && $arr[$j] > $key; $j -= $gap) { $arr[$j + $gap] = $arr[$j]; $arr[$j] = $key; } } } $gap = intval($gap / $step); } return $arr; } ~~~ # 堆排序 堆排序是指利用堆這種數據結構所設計的一種排序算法。 堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。 堆排序的平均時間復雜度為Ο(nlogn) 。 1. 創建一個堆`H[0..n-1]`； 2. 把堆首（最大值）和堆尾互換； 3. 把堆的尺寸縮小`1`，并調用`shift_down(0)`，目的是把新的數組頂端數據調整到相應位置； 4. ?重復步驟`2`，直到堆的尺寸為`1`。 ~~~php /** * 堆排序 * * @param array $lists * @return array */ function heap_sort(array $lists) { $n = count($lists); build_heap($lists); while (--$n) { $val = $lists[0]; $lists[0] = $lists[$n]; $lists[$n] = $val; heap_adjust($lists, 0, $n); //echo "sort: " . $n . "\t" . implode(', ', $lists) . PHP_EOL; } return $lists; } function build_heap(array &$lists) { $n = count($lists) - 1; for ($i = floor(($n - 1) / 2); $i >= 0; $i--) { heap_adjust($lists, $i, $n + 1); //echo "build: " . $i . "\t" . implode(', ', $lists) . PHP_EOL; } //echo "build ok: " . implode(', ', $lists) . PHP_EOL; } function heap_adjust(array &$lists, $i, $num) { if ($i > $num / 2) { return; } $key = $i; $leftChild = $i * 2 + 1; $rightChild = $i * 2 + 2; if ($leftChild < $num && $lists[$leftChild] > $lists[$key]) { $key = $leftChild; } if ($rightChild < $num && $lists[$rightChild] > $lists[$key]) { $key = $rightChild; } if ($key != $i) { $val = $lists[$i]; $lists[$i] = $lists[$key]; $lists[$key] = $val; heap_adjust($lists, $key, $num); } } ~~~