程序员经验分享-hwhale

快速排序算法的发明者霍尔

2023-05-16

图片来源:wikipedia

霍尔介绍

霍尔 (Sir Charles Antony Richard Hoare) 是一位英国计算机科学家，他也是著名的快速排序算法的发明者。他出生于斯里兰卡，1956年毕业于牛津大学。然后的两年里他服役于英国皇家海军，主要工作任务是研究俄国的现代军事，并因为这个原因开始学习俄语。在他结束服役后，他以研究生的身份进入莫斯科大学主攻计算机翻译。在莫斯科学习的一年中，因为偶然的机会他为参加展览的公司Elliott Brothers充当翻译。当他回国后，这家公司立即聘用了他，因为霍尔会俄语的缘故，公司还为他增加了工资。

快速排序算法起源

1960年代，英国国家物理实验室 (National Physical Laboratory) 开始了一项新的计划：将俄文自动翻译成英文。正好霍尔有这个经历，他与俄国的机器翻译专家相识，还在“机器翻译”(Machine Translation) 上发表过论文。于是他在那里得到了一份工作。

在那个年代，俄文到英文的词汇列表是以字母顺序存储在一条长长的磁带上的。因此，当有一段俄文句子需要翻译时，第一步是把这个句子的词按照同样的顺序排列。这样机器就可以在磁带上只走一遍就可以找到所有的翻译。霍尔意识到，他必须找出一种能在计算机上实现的排序的算法来。他想到的第一个算法是后人称作“冒泡排序 (bubble sort)”的算法。虽然他没有声明这个算法是他发明的，但他显然是独自得到这个算法的。他很快放弃了这个算法，因为它的速度比较慢。用计算复杂度理论 (Computational complexity theory) 来说，它平均需要 O(n2) 次运算。快速排序 (Quicksort) 是霍尔想到的第二个算法。这个算法的计算复杂度是 O(nlogn) 次运算。当 n 特别大的时候，显然步骤要少很多。

霍尔的其他建树

  • 霍尔本人被称为“影响算法世界的十位大师之一”
  • 由霍尔发明的快速排序算法被称为“二十世纪十大算法之一”
  • 霍尔领导了Algol 60第一个商用编译器的设计与开发，由于其出色的成绩，最终成为该公司首席科学家
  • 因霍尔对Algol 60程序设计语言理论、互动式系统及APL的贡献，1980年被美国计算机协会授予“图灵奖”
  • 2000年因为其在计算机科学与教育上做出的贡献被封为爵士

说明

  • 本篇文章参考了该文章《霍尔和快速排序法》。链接如下：http://blog.sciencenet.cn/blog-420554-552107.html
  • 如有侵权，请随时联系我，立马删除
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

快速排序算法的发明者霍尔 的相关文章

  • React G2Plot 水波图

    官方文档 xff1a https antv g2plot v1 gitee io zh docs manual introduction 安装依赖 span class token function npm span span class

  • 数据链路层

    本篇目录 数据链路层的三个基本问题 使用点对点信道的数据链路层 使用广播信道的数据链路层 以太网MAC层的硬件地址 一 数据链路层的三个基本问题 封装成帧 xff1a 帧是数据链路层的传送单位 一个帧的帧长等于帧的数据部分加上帧的首部和尾部

  • 输入三个数求出最大值(5种方法)

    这是一个很简单的C语言程序 xff0c 重要的是考验思考问题的角度 xff1a 方法1 xff1a include lt stdio h gt void main int a b c scanf 34 d d d 34 amp a amp

  • 把二维数组数据读入txt文本(C语言)

    我们经常需要把计算后的数据存入txt文本 xff0c 下例提供了一种简单思路 xff1a include lt stdio h gt include lt stdlib h gt int main int a 2 3 61 5 2 8 4

  • 查询txt文本信息行数(C和C++分别实现)

    在一些程序设计中 xff0c 我们经常要先查询txt文本的行数 xff0c 据此 xff0c 才能对数组进行动态内存分配 C语言实现 include lt stdio h gt include lt stdlib h gt define A

  • 从txt中读取数据存入二维数组

    在实际应用中 xff0c 经常需要把txt中的数据读入到一个数组中 xff0c 然后再参与运算 在C语言中可以利用fscanf 函数从文件中读取数据 xff0c 示例如下 xff1a void main xff08 xff09 double

  • 仿射变换

    AffineTransform类描述了一种二维仿射变换的功能 xff0c 它是一种二维坐标到二维坐标之间的线性变换 xff0c 保持二维图形的 平直性 xff08 译注 xff1a straightness xff0c 即变换后直线还是直线

  • OpenCV下的直线拟合

    出处 xff1a http blog csdn net Tangyongkang OpenCV中 CvSeq 对象由以下语句生成 创建 CvSeq的容器对象 CvMemStorage storage 61 cvCreateMemStorag

  • 利用meshgrid函数绘制二维高斯函数曲面

    meshgrid函数用于根据给定的横纵坐标点生成坐标网格 xff0c 以便计算二元函数的取值 设二维高斯函数表达式为 xff1a 程序如下 xff1a u 61 10 0 1 10 v 61 10 0 1 10 U V 61 meshgri

  • 要想成功必备的9大好习惯 以及必须克服的9个坏习惯

    要想成功 必备 9 大好习惯 以及 必须克服的 9 个坏习惯 你想成功吗 xff1f 那就及早培养有利于成功的好习惯 习惯的力量是惊人的 xff0c 35岁以前养成的习惯决定着你是否成功 有这样一个寓言故事 一位没有继承人的富豪死后将自己的

  • 数据结构算法学习之路

    1 二分法竞猜商品价格 include lt stdio h gt include lt stdlib h gt int main int oldprice price 61 0 i 61 0 printf 34 请设置商品的真实价格 xf

  • React markdown 编辑器

    react markdown 是一款 github 上开源的适用于 react 的 markdown 组件 xff0c 可以基本实现 markdown 的功能 xff0c 且可以根据自己实际应用定制的 remark 组件 安装 安装 mar

  • ROS下IMU串口通讯接口（通用版）

    1 源码 include lt string gt include lt ros ros h gt 包含ROS的头文件 include lt sensor msgs JointState h gt include lt tf transfo

  • openrave安装 win7(10)

    1 软件安装 1 xff09 其中 xff0c boost 1 44需独立编译 xff0c 放到指定文件夹下 xff0c 例如 D boost 1 44 0 xff1b 2 xff09 ps 最大的坑在这里 xff0c 务必把msvc bo

  • 嵌入式常见的数据结构

    0 引言1 线性表1 1 顺序表1 1 1 定义类型1 1 2 相关操作1 1 3 相关操作的实现 1 2 链表1 2 1 定义类型1 2 2 相关操作1 2 3 相关操作的实现 2 栈2 1 顺序栈2 1 1 定义类型2 1 2 相关操作

  • vslam

    目录 隐藏 1 SLAM 介绍 1 1 什么是SLAM 1 2 SLAM与视觉里程计 xff08 Visual Odometry xff09 1 3 SLAM和SfM 2 主流开源SLAM方案 2 1 视觉传感器 2 2 激光传感器 2 3

  • 华为mate手机从解锁到root成功全步骤

    警告 请保持电量充足 xff0c 不然小心变砖 解锁手机会恢复出厂设置 xff0c 原因未知 xff08 伤心 xff0c 不想查了 xff09 xff0c 请需要解锁的diy爱好者 xff0c 自行备份数据 一 安装adb驱动 下载安装a

  • ＜Zhuuu_ZZ＞HIVE(十一)函数

    Hive内置函数 一 Hive函数分类二 字符函数二 类型转换函数和数学函数三 日期函数四 集合函数五 条件函数六 聚合函数和表生成函数6 1 聚合函数6 2 表生成函数 xff1a 输出可以作为表使用 一 Hive函数分类 从输入输出角度

  • 嵌入式软件工程师的自我修养: Cortex-M3 ARM代码编译，链接与启动过程深度分析

    本篇文章以武汉杰开科技的汽车级MCU芯片AC7811为硬件平台 xff0c 使用GNU GCC作为开发工具 详细分析Compile Link Loader的过程以及Image 二进制程序 启动的详细分析 整个过程分析涉及到RW可读写DATA

  • STM32F103C8T6驱动ESP8266转串口模块（一）——模块AP模式+TCP客户端的HAL库驱动代码详解（CubeMX工程）

    1 STM32驱动ESP8266模块 笔者所使用的ESP8266模块为正点原子开发的模块 xff0c 该模块将通信接口变成了串口 接下来关于ESP8266模块的介绍均以此模块为基础 1 1 CubeMX配置STM32F103C8T6芯片引脚

随机推荐

  • spring cloud 问题记录（十五） Unauthorized grant type: authorization_code

    在使用授权码的方式获取code的时候出现如下异常 xff1a org springframework security oauth2 common exceptions InvalidClientException Unauthorized

  • 如何提高MATLAB的运算速度

    将提高MATLAB运算速度的途径总结为以下几点 xff1a 1 硬件方面 xff1a CPU配置高一些 xff1b 2 利用Profiler评估程序 xff0c 查找出函数花费时间较多的地方优化 xff1b 3 尽量少使用for或者whil

  • webpack5 学习系列 —— 支持 Vue

    接之前的 webpack 学习系列 安装 Vue xff1a span class token function npm span i vue S 安装完成 xff1a 安装相关插件 xff1a vue loader xff1a 解析和转换

  • Keil : Error-Flash Download failed Cortex-M4错误解决方案整理（J-Flash擦除下载教程）

    记录一下碰到的问题解决方法 第一步 xff1a 首先最先要确定的是芯片和设置是否对应 xff01 xff01 xff01 xff01 xff01 xff01 xff01 xff01 xff01 第二步 xff1a 确定芯片和设置对应无误后

  • js闭包理解与基本实现

    简单理解 xff1a 闭包就是 61 内层函数 43 外层函数的变量 内层函数 用到了外层函数的变量 所以才会产生了闭包 lt script gt function fn let a 61 1 function f console log

  • 头文件atlstr.h使用错误问题

    我的代码编译时出现如下错误 xff1a Error 33 fatal error LNK1120 1 unresolved externals Error 32 error LNK2001 unresolved external symbo

  • ubuntu编译服务器搭建

    我们现在开始做Android项目 xff0c 编译Android源码必不可少 但是Android编译需要Linux平台 xff08 一般都采用ubuntu xff09 xff0c 而且各种环境搭建繁杂 xff0c 编译时间长 xff0c 占

  • 和程序员有些不解之缘

    没来由的想起九年前的六月七 xff0c 不管是谁或许都不会想到一个青涩俏皮的丫头会变成铁铮铮的 汉子 高考那年我没发现自己有些许紧张 xff0c 在那之前我几乎没带着脑袋活着 xff08 我是那么想的 xff09 xff0c 觉着自己不在乎

  • SWDL学习篇

    WSDL 学习篇 1 什么是WSDL WSDL 是网络服务描述语言 xff0c 使用xml 编写 xff0c 是xml 文档 xff0c 可规定服务的位置以及提供服务的操作和方法 2 WSDL 文档结构 1 lt portType gt 元

  • linux面试题

    1 在Linux系统中 以 文件 方式访问设备 2 Linux内核引导时 从文件 etc fstab 中读取要加载的文件系统 3 Linux文件系统中每个文件用 i节点 来标识 4 全部磁盘块由四个部分组成 分别为 引导块 专用块 i节点表

  • MySql学习笔记（一）MySql卸载和安装说明

    MySql卸载 开始 控制面板 程序和功能 MySQL server xx 卸载 删除 C Program Files x86 MySQL 文件 删除 C ProgramData MySQL 文件 xff08 隐藏目录 xff09 如果以上

  • MySql学习笔记（二）MySql配置文件和服务操作说明

    Mysql配置文件说明 MySQL MySQL ServerX X my ini mysqld 为服务端配置 xff0c 服务端端口号 port 61 3306 安装目录 basedir 61 34 C Program Files MySQ

  • MySql学习笔记（三）MySql常用命令说明

    一 数据库命令 1 1显示数据库命令 命令 xff1a mysql gt show databases 执行后 xff1a 43 43 Database 43 43 information schema mysql performance

  • 什么是源端口和目的端口

    源端口就是指本地端口 目的端口就是远程端口 一个数据包 xff08 pocket xff09 被解封装成数据段 xff08 segment xff09 后就会涉及到 连接上层协议的端口问题 很多人都在源端口和目的端口这两个概念上犯迷糊 xf

  • Redux 学习系列（一） —— 基础概念入门篇

    简介 Redux 是一个可预测的 JavaScript 应用状态管理容器 xff0c 也可以说是一个应用数据流框架 作用 Redux 主要是用作应用状态的管理 它抽离所有组件的状态 xff0c 构造一个中心化的单独常量状态树 xff08 对

  • ini文件

    关于ini 文件的存储于加载 xff0c 初次遇到 xff0c 刚接触ini 文件 xff0c 我想我该把它记下 xff0c 以后提醒自己要常用 参数 保存 xff1a 参数结构体 struct TextConfig int nVol 音量

  • TX2安装Realsense -L515相机并在ros下 运行 总结

    1 写在最前面 坑爹呀有木有 xff0c L515 刚弄出来 xff0c 导师就让用 一堆坑呀 xff0c 最大的谎言就是ubuntu1604能用realsense2 不管之前D435之流留下多少恩爱情仇 xff0c https www i

  • 12-IDEA配置JDK版本（2020.2.3版本）

    1 配置当前项目的JDK版本 File gt Project Structure gt Project SDKs xff0c 也可以直接点击右上角的图标 2 配置之后创建的新项目JDK版本 类似于全局配置 File gt New Proje

  • 傅立叶变换详解

    傅里叶变换 傅里叶变换 xff08 Fourier transform xff09 是一种线性的积分变换 xff0c 从时间转换为频率的变化 1 连续傅里叶变换 这是将频率域的函数F 表示为时间域的函数f xff08 t xff09 的积分

  • 快速排序算法的发明者霍尔

    霍尔介绍 霍尔 Sir Charles Antony Richard Hoare 是一位英国计算机科学家 xff0c 他也是著名的快速排序算法的发明者 他出生于斯里兰卡 xff0c 1956年毕业于牛津大学 然后的两年里他服役于英国皇家海军

热门标签