冒泡排序
逐行对比，满足条件则交换。
时间复杂度：O(n^2)
/**
* 冒泡排序
* @param array $arr 排序数组
* @param bool $sort 排序方式：true=升序，false=降序
* @return array|bool
*/
function bubble_sort(array $arr, bool $sort = true)
{
if (empty($arr)) return false;
//默认有序
$sort_leb = true;
$arr_length = count($arr);
for ($i = 0; $i < $arr_length; $i++) {
//对比次数随循环减少
for ($j = 0; $j < ($arr_length - $i - 1); $j++) {
//执行判断
$order_leb = $sort ? $arr[$j] > $arr[$j + 1] : $arr[$j] < $arr[$j + 1];
if ($order_leb) {
//首次对比，判断是否有序
$sort_leb = false;
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
unset($temp);
}
}
if ($sort_leb) break;
}
return $arr;
}
var_dump(bubble_sort([42, 63, 67, 123, 6, 75, 324, 6, 8, 34, 24, 35, 64, 6, 7, 5, 246, 34, 5],false));
exit();
选择排序
遍历第一遍完记录最小的数，放到第一个位置；再次遍历记录剩余列表中的最小的数，继续放置。
时间复杂度：O(n^2)
/**
* 选择排序
* @param array $arr
* @return array
*/
function select_sort(array $arr)
{
for ($i = 0; $i < count($arr) - 1; $i++) {
$min = $i;
for ($j = $i + 1; $j < count($arr); $j++) {
if ($arr[$j] < $arr[$min]) $min = $j;
}
$temp = $arr[$min];
$arr[$min] = $arr[$i];
$arr[$i] = $temp;
unset($temp);
}
return $arr;
}
插入排序
元素被分为有序区和无序区两部分。最初有序区只有一个元素。每次从无序区中选择一个元素，插入到有序区的位置，直到无序区变空。
时间复杂度：O(n^2)
/**
* 插入排序
* @param array $arr
* @return array
*/
function insert_sort(array $arr)
{
$arr_length = count($arr);
//外层循环用于从未排序区域中取出待排序元素
for ($i = 1; $i < $arr_length; $i++) {
$temp = $arr[$i];
//内层循环用于从已排序区域寻找待排序元素的插入位置
for ($j = $i - 1; $j >= 0; $j--) {
if ($temp < $arr[$j]) {
$arr[$j + 1] = $arr[$j];
$arr[$j] = $temp;
} else {
//无需再排序
break;
}
}
unset($temp);
}
return $arr;
}
快速排序
设置一个初始中间值，将需要排序的数组分成左中右三块，左<中<右，然后递归用相同的方式来排序左边和右边，最后合并数组。
时间复杂度：O (nlogn)
/**
* 快速排序
* @param array $arr
* @return array
*/
function quick_sort(array $arr)
{
//判断是否需要运行，因下面已拿出一个中间值，这里<=1
$arr_length = count($arr);
if ($arr_length <= 1) return $arr;
$middle = $arr[0]; // 中间值
$left = []; // 接收小于中间值
$right = [];// 接收大于中间值
// 循环比较
for ($i = 1; $i < $arr_length; $i++) {
if ($middle < $arr[$i]) {
$right[] = $arr[$i];
} else {
$left[] = $arr[$i];
}
}
//递归划分为2边
$left = quick_sort($left);
$right = quick_sort($right);
// 合并排序后的数据，别忘了合并中间值
return array_merge($left, [$middle], $right);
}
归并排序
归并排序：就是利用归并（合并）的思想实现的排序方法。它的原理是假设初始序列含有 n 个元素，则可以看成是 n 个有序的子序列，每个子序列的长度为 1，然后两两归并，得到 ⌈ n / 2⌉ （⌈ x ⌉ 表示不小于 x 的最小整数）个长度为 2 或 1 的有序序列；再两两归并，······，如此重复，直至得到一个长度为 n 的有序序列为止，这种排序方法就成为 2 路归并排序。
时间复杂度：O (nlogn)
/**
* 归并排序
* @param array $arr
* @return array
*/
function merge_sort(array $arr){
if (count($arr) <= 1) {
return $arr;
}
$left = array_slice($arr, 0, (int)(count($arr) / 2));
$right = array_slice($arr, (int)(count($arr) / 2));
$left = merge_sort($left);
$right = merge_sort($right);
$output = merge($left, $right);
return $output;
}
function merge($left, $right){
$result = [];
while (count($left) > 0 && count($right) > 0) {
if ($left[0] <= $right[0]) {
array_push($result, array_shift($left));
} else {
array_push($result, array_shift($right));
}
}
array_splice($result, count($result), 0, $left);
array_splice($result, count($result), 0, $right);
return $result;
}
var_dump(merge_sort([42, 63, 67, 123, 6, 75, 324, 6, 8, 34, 24, 35, 64, 6, 7, 5, 246, 34, 5]));
exit();