排序算法

  1. $arr = [1, 8, 3, 6, 5, 4, 7, 2, 9];
  3. sort($arr); // 值由低到高
  4. rsort($arr); // 值由高到低
  5. asort($arr); // 键值关系保持值由低到高
  6. arsort($arr); // 键值关系保持值由高到低
  7. ksort($arr); // 键由低到高
  8. krsort($arr); // 键由高到低
  9. natsort($arr); // 值自然排序
  10. natcasesort($arr); // 大小写不敏感值自然排序
  11. shuffle($arr); // 值随机
  12. array_multisort($arr); // 键值关系保持值由低到高
  14. // 自定义排序
  15. $uFn = function ($a, $b) {
  16.   if ($a === $b) {
  17.     return 0;
  18.   } else {
  19.     return $a >= $b ? -1 : 1;
  20.   }
  21. };
  22. usort($arr, $uFn);
  23. uasort($arr, $uFn);
  24. uksort($arr, $uFn);

冒泡排序

时间复杂度查找排序算法 - 图1。

  1. $arr = [1, 8, 3, 6, 5, 4, 7, 2, 9];
  3. $len = count($arr);
  4. for($i = 0; $i < $len - 1; $i++){ // 控制内层循环范围
  5.   for($j = 0; $j < $len - 1 - $i; $j++){ // 先处理末位，依次往前排
  6.     // 大的往后冒泡
  7.     if ($arr[$j] > $arr[$j + 1]) {
  8.       $tmp = $arr[$j];
  9.       $arr[$j] = $arr[$j + 1];
  10.       $arr[$j + 1] = $tmp;
  11.     }
  12.   }
  13. }
  15. print_r($arr);

选择排序

时间复杂度查找排序算法 - 图2。

  1. $arr = [1, 8, 3, 6, 5, 4, 7, 2, 9];
  3. $len = count($arr);
  4. for ($i = 0; $i < $len - 2; $i++) {
  5.   $minPos = $i; // 先选定初始为最小值
  6.   for ($j = $i + 1; $j < $len; $j++) { // 与之后的值依次比较
  7.     // 遇到更小的，则更新为更小值
  8.     if ($arr[$j] < $arr[$minPos]) {
  9.       $minPos = $j;
  10.     }
  11.   }
  12.   // 替换最小值与初始位置
  13.   $tmp = $arr[$i];
  14.   $arr[$i] = $arr[$minPos];
  15.   $arr[$minPos] = $tmp;
  16. }
  18. print_r($arr);

查找算法

  1. $arr = [1, 8, 3, 6, 5, 4, 7, 2, 9];
  3. in_array(1, $arr); // 查找数组中是否存在某数据
  4. array_search(3, $arr); // 查找给定数据，查到返回键值
  5. array_key_exists("key", $arr); // 键名/索引查找

二分查找

时间复杂度查找排序算法 - 图3。

  1. $arr = [1, 8, 3, 6, 5, 4, 7, 2, 9];
  2. sort($arr); // 二分查找对象得是排好序的数组
  4. function binary_search(array $arr, int $val): int|bool
  5. {
  6.   $len = count($arr);
  8.   if ($val <= $arr[0] || $val >= $arr[$len - 1]) {
  9.     if ($val === $arr[0]) { // 等于最小值
  10.       return 0;
  11.     } elseif ($val === $arr[$len - 1]) { // 等于最大值
  12.       return $len - 1;
  13.     } else {
  14.       return false; // 超出范围
  15.     }
  16.   } else {
  17.     $halfSub = round($len / 2);
  18.     if ($val < $arr[$halfSub]) {
  19.       return binary_search(array_slice($arr, 0, $halfSub), $val);
  20.     } else {
  21.       return binary_search(array_slice($arr, $halfSub, $len), $val);
  22.     }
  23.   }
  24. }
  25. print(binary_search($arr, 1));