第十二章：实战二：数组操作与排序算法-PHP程序员面试算法宝典

当前位置:　首页>> 技术小册>> PHP程序员面试算法宝典

### 第十二章：实战二：数组操作与排序算法

在PHP程序员的职业生涯中，数组操作与排序算法是不可或缺的技能。无论是处理用户输入、管理数据集合，还是优化性能，深入理解并掌握这些技术都是至关重要的。本章将深入探讨PHP中数组的高级操作技巧以及几种常用的排序算法，旨在帮助读者在面试和实际开发中能够游刃有余地应对各种挑战。

#### 一、数组操作基础回顾

在开始深入探讨之前，我们先简要回顾一下PHP中数组的基本操作，包括创建、访问、遍历及修改数组等基础知识。

- **创建数组**：PHP支持索引数组和关联数组。索引数组使用数字索引，而关联数组则使用字符串键名。
  ```php
  // 索引数组
  $numbers = array(1, 2, 3, 4, 5);
  // 关联数组
  $people = array("name" => "John", "age" => 30, "city" => "New York");
  // PHP 5.4+ 简洁语法
  $numbers = [1, 2, 3, 4, 5];
  $people = ["name" => "John", "age" => 30, "city" => "New York"];
  ```

- **访问元素**：使用索引或键名访问数组元素。
  ```php
  echo $numbers[0]; // 输出 1
  echo $people["name"]; // 输出 John
  ```

- **遍历数组**：使用`foreach`循环遍历数组。
  ```php
  foreach ($numbers as $number) {
      echo $number . PHP_EOL;
  }
  foreach ($people as $key => $value) {
      echo "$key: $value" . PHP_EOL;
  }
  ```

- **修改数组**：通过索引或键名直接修改元素值，或使用函数如`array_push()`, `array_merge()`等。

#### 二、高级数组操作

##### 1. 数组搜索

- **array_search()**：搜索数组中给定的值，如果成功则返回相应的键名。
  ```php
  $key = array_search(3, $numbers); // $key 为 2
  ```

- **array_keys() 和 array_values()**：分别返回数组所有的键名和值。

##### 2. 数组过滤

- **array_filter()**：使用回调函数过滤数组中的元素。
  ```php
  $filtered = array_filter($numbers, function($value) {
      return $value > 2;
  });
  // $filtered 为 [3, 4, 5]
  ```

##### 3. 数组映射

- **array_map()**：将回调函数作用到给定数组的每个值上，返回包含所有回调函数返回值的数组。
  ```php
  $squared = array_map(function($value) {
      return $value * $value;
  }, $numbers);
  // $squared 为 [1, 4, 9, 16, 25]
  ```

##### 4. 数组归约

- **array_reduce()**：迭代地将回调函数作用到数组的每个值上，将结果汇总为单一的值。
  ```php
  $sum = array_reduce($numbers, function($carry, $item) {
      return $carry + $item;
  }, 0);
  // $sum 为 15
  ```

#### 三、排序算法

排序算法是数组操作中的核心部分，它们决定了数据处理的效率和性能。以下介绍几种常用的排序算法及其在PHP中的实现。

##### 1. 冒泡排序（Bubble Sort）

冒泡排序是最简单的排序算法之一，通过重复遍历要排序的数组，比较相邻元素，如果它们的顺序错误就把它们交换过来。遍历数组的工作是重复进行直到没有再需要交换，也就是说该数组已经排序完成。

```php
function bubbleSort(&$arr) {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                // 交换 $arr[$j] 和 $arr[$j+1]
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
}
```

##### 2. 选择排序（Selection Sort）

选择排序算法的基本思想是：第1次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的元素中选择最小（或最大）的元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素排完。

```php
function selectionSort(&$arr) {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$j] < $arr[$minIndex]) {
                $minIndex = $j;
            }
        }
        // 交换 $arr[$i] 和 $arr[$minIndex]
        $temp = $arr[$i];
        $arr[$i] = $arr[$minIndex];
        $arr[$minIndex] = $temp;
    }
}
```

##### 3. 插入排序（Insertion Sort）

插入排序的工作方式是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到$O(1)$的额外空间的排序）。

```php
function insertionSort(&$arr) {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;

while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j = $j - 1;
        }
        $arr[$j + 1] = $key;
    }
}
```

##### 4. 快速排序（Quick Sort）

快速排序是一种分治策略的排序算法。它将一个数组分为两个子数组，将两个子数组分别排序。

```php
function quickSort(&$arr, $low, $high) {
    if ($low < $high) {
        $pi = partition($arr, $low, $high);

quickSort($arr, $low, $pi - 1);
        quickSort($arr, $pi + 1, $high);
    }
}

function partition(&$arr, $low, $high) {
    $pivot = $arr[$high];
    $i = ($low - 1);

for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;

// 交换 $arr[$i] 和 $arr[$j]
            $temp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $temp;
        }
    }

// 交换 $arr[$i+1] 和 $arr[$high] (或 pivot)
    $temp = $arr[$i + 1];
    $arr[$i + 1] = $arr[$high];
    $arr[$high] = $temp;

return $i + 1;
}
```

#### 四、PHP内置排序函数

除了手动实现排序算法外，PHP还提供了一系列内置的排序函数，如`sort()`, `asort()`, `arsort()`, `ksort()`, `krsort()`, `usort()`, `uasort()`, `uksort()`等，它们提供了更加便捷和高效的排序方式。了解并合理使用这些函数，可以大大提高开发效率。

#### 五、总结

本章详细介绍了PHP中数组的高级操作技巧以及几种常见的排序算法。通过实践这些技术和算法，你可以更好地理解和处理PHP中的数组数据，从而在面试和实际开发中展现出更加专业的技能水平。记住，理论知识是基础，但实践才是检验真理的唯一标准。多动手练习，多思考总结，你的PHP技能将会得到质的飞跃。

该分类下的相关小册推荐：

PHP合辑1-基础入门

PHP8入门与项目实战（7）

PHP合辑5-SPL标准库

PHP高性能框架-Swoole

PHP8入门与项目实战（6）

PHP8入门与项目实战（1）

PHP合辑2-高级进阶

Magento零基础到架构师(库存管理)

Yii2框架从入门到精通(中)

PHP底层原理及源码分析

全栈工程师修炼指南

Magento2主题开发高级实战