冒泡排序
- 兩兩比較, 講逆序的兩個(gè)數(shù)交換位置
// 冒泡排序, 時(shí)間復(fù)雜度O(N^2)
for ($i = 0; $i < count($arr); $i++)
{
for ($j = $i; $j < count($arr); $j++)
{
if ($arr[$i] > $arr[$j])
{
$temp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $temp;
}
}
}
快速排序
- 選擇一個(gè)基準(zhǔn)元素, 講數(shù)組里的數(shù)與之比較, 區(qū)分出比之大的和比之小的兩部分, 并分別對(duì)這兩部分遞歸執(zhí)行上述操作
/**
* 選中數(shù)組中的某一值,比較將比該數(shù)大的放在右邊,比該數(shù)小的放在左邊,然后對(duì)左右兩個(gè)數(shù)組繼續(xù)執(zhí)行上述操作
* 時(shí)間復(fù)雜度 O(NlogN）
*/
public function quick_sort($arr)
{
if (count($arr) < 2) return $arr;
$left_arr = [];
$right_arr = [];
$key = $arr[0];
// 從第二個(gè)數(shù)開(kāi)始比較
for ($i = 1; $i < count($arr); $i++)
{
if ($arr[$i] <= $key)
{
$left_arr[] = $arr[$i];
}
else
{
$right_arr[] = $arr[$i];
}
}
$left_arr = $this->quick_sort($left_arr); //遞歸排序yuansu
$right_arr = $this->quick_sort($right_arr);
return array_merge($left_arr, [$key], $right_arr);
}
插入排序
- 選擇一個(gè)要排序元素, 從該元素之前的最后一位開(kāi)始比較, 如果逆序就插入到其前面
// 插入排序, 時(shí)間復(fù)雜度 O(N^2)
for ($i = 1; $i < count($arr); $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;
}
}
}
選擇排序
- 每次找到要排序數(shù)組的還未排序部分的最小值將之放在已排序部分的最后面
// 選擇排序, 時(shí)間復(fù)雜度O(N^2)
for ($i = 0; $i < count($arr); $i++)
{
$temp = $arr[$i];
$index = $i;
for ($j = $i; $j < count($arr); $j++)
{
if ($arr[$j] < $temp)
{
$index = $j;
}
}
if ($i != $index)
{
$arr[$i] = $arr[$index];
$arr[$index] = $temp;
}
}
