PHP 7: 真实世界的应用开发
  • 前言
  • 模块一
    • 第一章、建立基础
      • PHP 7 安装注意事项
      • 使用内置的 PHP web 服务器
      • 创建一个 MySQL 测试数据库
      • 安装 PHPUnit
      • 实现类的自动加载
      • 抓取一个网站
      • 建立一个深度网络扫描器
      • 创建一个 PHP 5 到 PHP 7 代码转换器
    • 第二章、使用 PHP 7 高性能特性
      • 了解抽象语法树
      • 理解句法分析中的差异
      • 理解 foreach() 处理中的差异
      • 使用 PHP 7 增强功能提高性能
      • 遍历海量文件
      • 将电子表格上传到数据库
      • 递归目录迭代器
    • 第三章、使用 PHP 函数
      • 函数开发
      • 数据类型提示
      • 使用返回值数据类型
      • 使用迭代器
      • 使用生成器编写自己的迭代器
    • 第四章、使用 PHP 面向对象程序设计
      • 类的开发
      • 类的扩展
      • 使用静态属性和方法
      • 使用命名空间
      • 定义可见性
      • 使用接口
      • 使用特性
      • 实现匿名类
    • 第五章、与数据库的交互
      • 使用PDO连接数据库
      • 构建一个 OOP SQL 查询生成器
      • 处理分页
      • 定义实体以匹配数据库表
      • 将实体类与RDBMS查询绑定
      • 将二次查找嵌入到查询结果中
      • 实现jQuery DataTables的PHP查找
    • 第六章、建立可扩展的网站
      • 创建通用表单元素生成器
      • 创建一个HTML单选元素生成器
      • 创建一个HTML选择元素生成器
      • 实现表单工厂
      • 链式 $_POST 过滤器
      • 链式 $_POST 验证器
      • 将验证绑定到表单
    • 第七章、访问Web服务
      • 在PHP和XML之间转换
      • 创建一个简单的REST客户端
      • 创建一个简单的REST服务器
      • 创建一个简单的SOAP客户端
      • 创建一个简单的SOAP服务器
    • 第八章、处理日期/时间和国际化方面
      • 在视图脚本中使用 emoji
      • 转换复杂字符
      • 从浏览器数据获取语言环境
      • 按地区设置数字格式
      • 按地区处理货币
      • 按地区设置日期/时间格式
      • 创建一个HTML国际日历生成器
      • 构建一个周期性事件生成器
      • 不使用gettext处理翻译
    • 第九章、开发中间件
      • 使用中间件进行认证
      • 使用中间件实现访问控制
      • 使用高速缓存提高性能
      • 实施路由选择
      • 进行框架间的系统调用
      • 使用中间件来跨语言
    • 第十章、高级算法
      • 使用 getter 和 setter
      • 实现一个链表
      • 建立冒泡排序
      • 实现一个堆栈
      • 构建一个二分法查找类
      • 实现一个搜索引擎
      • 显示多维数组并累计总数
    • 第十一章、软件设计模式的实现
      • 创建数组到对象的转化器
      • 构建对象到数组到转化器
      • 实施策略模式
      • 定义一个映射器
      • 实现对象关系映射
      • 实施发布/订阅设计模式
    • 第十二章、提高网站安全
      • 过滤$_POST数据
      • 验证$_POST数据
      • 保护PHP session
      • 用令牌保护表格的安全
      • 建立一个安全的密码生成器
      • 带有验证码的安全保护表格
      • 不使用mcrypt进行加密/解密
    • 第十三章、最佳实践、测试和调试
      • 使用特征和接口
      • 通用异常处理程序
      • 通用错误处理程序
      • 编写一个简单的测试
      • 编写测试套件
      • 生成虚假的测试数据
      • 使用session_start参数自定义会话
    • PSR-7
  • 模块二
  • 模块三
    • GoF 设计模式
      • 结构型
      • 行为型
      • 小结
    • SOLID 设计原则
      • 开闭原则
      • 里氏替换原则
      • 接口隔离原则
      • 依赖反转原则
      • 小结
    • 模块化网店应用的需求规范
      • 线框设计
      • 定义技术栈
      • 小结
    • Symfony 概述
      • 创建一个空白项目
      • 使用 Symfony 控制台
      • 控制器
      • 路由
      • 模板
      • 表单
      • 配置 Symfony
      • bundle 系统
      • 数据库和 Doctrine
      • 测试
      • 验证
      • 小结
    • 构建核心模块
    • 构建目录模块
    • 构建客户模块
    • 构建支付模块
    • 构建发货模块
    • 构建销售模块
    • 总结
由 GitBook 提供支持
在本页
  • 如何做...
  • 如何运行...
  1. 模块一
  2. 第十章、高级算法

建立冒泡排序

上一页实现一个链表下一页实现一个堆栈

最后更新于4年前

经典的冒泡排序是经常分配给大学生的练习。尽管如此,掌握这个算法还是很重要的,因为在很多场合,PHP内置的排序函数并不适用。一个例子是对一个多维数组进行排序,而排序键不是第一列。

冒泡排序的工作方式是递归迭代列表,并将当前值与下一个值交换。如果你想让项目按升序排列,如果下一个项目小于当前项目,就会发生交换。对于降序,如果相反,则会发生交换。当不再发生交换时,排序就结束了。

在下图中,第一次通关后,葡萄和香蕉互换,橙子和樱桃也互换。第2次通过后,葡萄和樱桃被交换。最后一关不再发生交换,冒泡排序结束。

如何做...

1.我们不希望实际移动数组中的值,那样在资源使用方面会非常昂贵。取而代之的是,我们将使用一个链表,这在前面的示例中已经讨论过了。

​2. 首先我们使用前面示例中讨论的 buildLinkedList() 函数建立一个链表。

3. 然后我们定义了一个新的函数 bubbleSort(),它通过引用接受链表、主列表、排序字段和一个代表排序顺序(升序或降序)的参数。

function bubbleSort(&$linked, $primary, $sortField, $order = 'A')
{

4. 需要的变量包括一个代表迭代次数、交换次数和基于链表的迭代器。

  static $iterations = 0;
  $swaps = 0;
  $iterator = new ArrayIterator($linked);

5. 在 while() 循环中,我们只有在迭代仍然有效的情况下才会继续,也就是说仍然在进行中。然后我们获得当前的键和值,以及下一个键和值。请注意额外的if()语句,以确保迭代仍然有效(也就是说,确保我们不会从列表末尾掉下来!)。

while ($iterator->valid()) {
  $currentLink = $iterator->current();
  $currentKey  = $iterator->key();
  if (!$iterator->valid()) break;
  $iterator->next();
  $nextLink = $iterator->current();
  $nextKey  = $iterator->key();

6. 接下来我们检查排序是升序还是降序。根据方向的不同,我们检查下一个值是否大于或小于当前值。比较的结果存储在 $expr 中。

if ($order == 'A') {
    $expr = $primary[$linked->offsetGet
            ($currentKey)][$sortField] > 
            $primary[$linked->offsetGet($nextKey)][$sortField];
} else {
    $expr = $primary[$linked->offsetGet
            ($currentKey)][$sortField] < 
            $primary[$linked->offsetGet($nextKey)][$sortField];
}

7. 如果$expr 的值为TRUE,并且我们有有效的当前键和下一个键,那么这些值就会在链表中进行交换。我们也会对 $swaps 进行增量。

if ($expr && $currentKey && $nextKey 
    && $linked->offsetExists($currentKey) 
    && $linked->offsetExists($nextKey)) {
    $tmp = $linked->offsetGet($currentKey);
    $linked->offsetSet($currentKey, 
    $linked->offsetGet($nextKey));
    $linked->offsetSet($nextKey, $tmp);
    $swaps++;
  }
}

8. 最后,如果发生了任何交换,我们需要再次进行迭代,直到不再有交换。据此,我们对同一方法进行递归调用。

if ($swaps) bubbleSort($linked, $primary, $sortField, $order);

9. 真正的返回值是重新组织的链表。我们还返回迭代次数,只是为了参考。

  return ++$iterations;
}

如何运行...

将前面讨论过的 bubbleSort() 函数添加到前面的示例中创建的 include 文件中。你可以使用前面的示例中讨论的相同逻辑来读取 customer.csv 文件,生成一个主列表。

<?php
define('CUSTOMER_FILE', __DIR__ . '/../data/files/customer.csv');
include __DIR__ . '/chap_10_linked_list_include.php';
$headers = array();
$customer = readCsv(CUSTOMER_FILE, $headers);

然后,可以使用第一列作为排序键生成一个链表。

$makeLink = function ($row) {
  return $row[0];
};
$linked = buildLinkedList($customer, $makeLink);

最后,调用 bubbleSort() 函数,提供链表和客户列表作为参数。你也可以提供一个排序列,在这个插图中第2列,代表账户余额,用字母 A 表示升序。printCustomer() 函数可以用来显示输出。

echo 'Iterations: ' . bubbleSort($linked, $customer, 2, 'A') . PHP_EOL;
echo printCustomer($headers, $linked, $customer);

下面是一个输出的例子。