一律杠、插入排序
1.排序思想
插入排序(InsertionSort)潭流，一般也被稱為直接插入排序竞惋。對于少量元素的排序，它是一個有效的算法灰嫉。
插入排序是一種最簡單的排序方法拆宛，它的基本思想是將一個記錄插入到已經(jīng)排好序的有序表中，從而一個新的讼撒、記錄數(shù)增 1 的有序表浑厚。在其實現(xiàn)過程使用雙層循環(huán)，外層循環(huán)對除了第一個元素之外的所有元素根盒，內(nèi)層循環(huán)對當前元素前面有序表進行待插入位置查找钳幅，并進行移動。
2.代碼實現(xiàn)
function insertionSort($arr)
{
$arr_nums = count($arr);
for ($i=1; $i < $arr_nums; $i++) {
$temp = $arr[$i];
$j = $i;
while ($j > 0 && $arr[$j - 1] > $temp) {
$arr[$j] = $arr[$j - 1];
$arr[$j - 1] = $temp;
$j--;
}
}
return $arr;
}
二炎滞、冒泡排序
1.排序步驟
- 比較相鄰的元素敢艰。如果第一個比第二個大，就交換他們兩個厂榛。
- 對每一對相鄰元素作同樣的工作盖矫，從開始第一對到結(jié)尾的最后一對。這步做完后击奶，最后的元素會是最大的數(shù)。
- 針對所有的元素重復以上的步驟责掏，除了最后一個柜砾。
- 持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較换衬。
2.代碼實現(xiàn)
function bubbleSort($arr)
{
$len = count($arr);
for ($i=0; $i < $len - 1; $i++) {
for ($j=0; $j < $len - 1 - $i; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
}
}
}
return $arr;
}
三痰驱、選擇排序
1.排序步驟
- 首先在未排序序列中找到最小（大）元素瞳浦，存放到排序序列的起始位置担映。
- 再從剩余未排序元素中繼續(xù)尋找最小（大）元素叫潦，然后放到已排序序列的末尾蝇完。
- 重復第二步，直到所有元素均排序完畢矗蕊。
2.代碼實現(xiàn)
public function selectionSort($array)
{
$len = count($array);
for ($i=0; $i < $len - 1; $i++) {
$maxIndex = $i;
for ($j = $i + 1; $j < $len; $j++) {
if ($array[$j] < $array[$maxIndex]) {
$maxIndex = $j;
}
}
$temp = $array[$i];
$array[$i] = $array[$maxIndex];
$array[$maxIndex] = $temp;
}
return $array;
}
四短蜕、快速排序
1.算法思想
快速排序使用分治法（Divide and conquer）策略來把一個串行（list）分為兩個子串行（sub-lists）。
快速排序又是一種分而治之思想在排序算法上的典型應用傻咖。本質(zhì)上來看朋魔，快速排序應該算是在冒泡排序基礎(chǔ)上的遞歸分治法。
2.排序步驟
- 從數(shù)列中挑出一個元素卿操，稱為 "基準"（pivot）;
- 重新排序數(shù)列若厚，所有元素比基準值小的擺放在基準前面惯豆，所有元素比基準值大的擺在基準的后面（相同的數(shù)可以到任一邊）检碗。在這個分區(qū)退出之后，該基準就處于數(shù)列的中間位置拓售。這個稱為分區(qū)（partition）操作；
- 遞歸地（recursive）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序洼裤；
3.代碼實現(xiàn)
public function quickSort($arr)
{
$len = count($arr);
if ($len <= 1) {
return $arr;
}
$middle = $arr[0];
$leftArray = [];
$rightArray = [];
for ($i = 1; $i < $len; $i++) {
if ($arr[$i] <= $middle) {
array_push($leftArray, $arr[$i]);
} else {
array_push($rightArray, $arr[$i]);
}
}
$leftArray = quickSort($leftArray);
array_push($leftArray, $middle);
$rightArray = quickSort($rightArray);
return array_merge($leftArray, $rightArray);
}
五邻辉、歸并排序
1.排序步驟
- 申請空間，使其大小為兩個已經(jīng)排序序列之和腮鞍，該空間用來存放合并后的序列值骇；
- 設定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置移国；
- 比較兩個指針所指向的元素吱瘩，選擇相對小的元素放入到合并空間，并移動指針到下一位置迹缀；
-重復步驟 3 直到某一指針達到序列尾使碾； - 將另一序列剩下的所有元素直接復制到合并序列尾。
2.代碼實現(xiàn)
public function mergeSort($arr)
{
$len = count($arr);
if ($len < 2) {
return $arr;
}
$middle = floor($len / 2);
$left = array_slice($arr, 0, $middle);
$right = array_slice($arr, $middle);
return merge(mergeSort($left), mergeSort($right));
}
public function merge($left, $right)
{
$result = [];
while (count($left) > 0 && count($right) > 0) {
if ($left[0] <= $right[0]) {
$result[] = array_shift($left);
} else {
$result[] = array_shift($right);
}
}
while (count($left)) {
$result[] = array_shift($left);
}
while (count($right)) {
$result[] = array_shift($right);
}
return $result;
}
