专栏首页yeedomliu《图解算法》第2章 选择排序

《图解算法》第2章 选择排序

第2章 选择排序

数组是个重要的主题,一定要高度重视!很多算法仅在数据经过排序后才管用

内存工作原理

  • 需要将数据存储到内存时,你请求计算机提供存储空间,计算机给你一个存储地址。需要存储多项数据时,有两种基本方式——数组和链表。但它们并非都适用于所有的情形,因此知道它们的差别很重要

数组和链表

有时候,需要在内存中存储一系列元素。假设你要编写一个管理待办事项的应用程序,为此需要将这些待办事项存储在内存中 使用数组意味着所有待办事项在内存中都是相连的。现在假设你要添加第四个待办事项,但后面的那个抽屉放着别人的东西!你需要重新请求计算机重新分配一块可容纳4个待办事项的内存,再将所有待办事项都移到那里

  • 一种解决之道是“预留座位”:即使当前只有3个待办事项,也请计算机提供10个位置,以防需要添加待办事项。它存在两个缺点
  1. 你额外请求的位置可能根本用不上,这将浪费内存。你没有使用,别人也用不了
  2. 待办事项超过10个后,你还得转移

链表

  • 链表中的元素可存储在内存的任何地方
  • 链表的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串在一起
  • 只要有足够的内存空间,就能为链表分配内存

数组

  • 需要同时读取所有元素时,链表的效率很高:你读取第一个元素,根据其中的地址再读取第二个元素,以此类推。但如果你需要跳跃,链表的效率真的很低
  • 需要阳春面地读取元素时,数组的效率很高,因为可迅速找到数组的任何元素

术语

元素的位置称为索引 数组和链表操作的运行时间

在中间插入

  • 使用链表时,插入元素很简单,只需修改它前面的那个元素指向的地址
  • 使用数组时,则必须将后面的元素都向后移。如果没有足够的空间,可能还得将整个数组复制到其他地方!因此,当需要在中间插入元素时,链表是更好的选择

删除

  • 链表也是更好的选择,因为只需修改前一个元素指向的地址即可
  • 使用数组时,删除元素后,必须将后面的元素都向前移
  • 不同于插入,删除元素总能成功。如果内存中没有足够的空间,插入操作可能失败,但在任何情况下都能够将元素删除
  • 数组和链表操作的运行时间
  • 数组用得很多,因为它支持随机访问。有两种访问方式
  1. 随机访问:
  2. 顺序访问:从第一个元素开始逐个读取元素;链表只能顺序访问,要读取链表第十个元素,得先读取前九个元素,并沿链接找到第十个元素

假设Facebook使用的是一种混合数据:链表数组。这个数组包含26个元素,每个元素都指向一个链表。这种新数据结构的查找和插入速度更快还是更慢?

选择排序

  • 选择排序是一种灵巧的算法,但其速度不是很快。快速排序是一种更快的排序算法,其运行时间为O(n log n)
class SelectionSort
{

    public static function sort($array) {
        $length = count($array);
        foreach ($array as $outerIndex => $item) {
            $minIndex = $outerIndex;
            for ($innerIndex = $outerIndex + 1; $innerIndex < $length; $innerIndex ++) {
                if ($array[ $minIndex ] > $array[ $innerIndex ]) {
                    $minIndex = $innerIndex;
                }
            }
            $temp = $array[ $outerIndex ];
            $array[ $outerIndex ] = $array[ $minIndex ];
            $array[ $minIndex ] = $temp;
        }

        return $array;
    }

}

$array = [5, 3, 6, 2, 10];
echo join(SelectionSort::sort($array), ',') . PHP_EOL;

// 输出:2,3,5,6,10

本文分享自微信公众号 - yeedomliu(yeedom_liu),作者:yeedomliu

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《为什么精英可以快速积累财富》第4章 把自己当作赚钱的“资本”——人力资本

    yeedomliu
  • 《最重要的事,只有一件》第三部分 成就卓越 释放你内在的潜力

    yeedomliu
  • 《这样读书就够了》前言

    yeedomliu
  • 前端课程——定位继承与层叠

    z- index属性指定了一个具有定位属性的元素及其子代元素的z -order。当元素之间重叠的时候,z-order决定哪一个 元素覆盖在其余元素的上方显示。通...

    Dreamy.TZK
  • JDK1.9-数据结构

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    cwl_java
  • 使用jQuery筛选排除元素以修改指定标签的属性

    1、eq()    筛选指定索引号的元素 2、first()  筛选出第一个匹配的元素 3、last()   筛选出最后一个匹配的元素 4、hasClas...

    山河木马
  • 读书笔记:《算法图解》第二章 选择排序选择排序:#

    孙亖
  • (47) 堆和PriorityQueue的应用 / 计算机程序的思维逻辑

    45节介绍了堆的概念和算法,上节介绍了Java中堆的实现类PriorityQueue,PriorityQueue除了用作优先级队列,还可以用来解决一些别的问题,...

    swiftma
  • 编程小白 | 每日一练(103)

    这道理放在编程上也一并受用。在编程方面有着天赋异禀的人毕竟是少数,我们大多数人想要从编程小白进阶到高手,需要经历的是日积月累的学习,那么如何学习呢?当然是每天都...

    闫小林
  • ​Java自动化测试 (元素定位 23)

    使用脚本断点调试定位是否正确是一个方法,当时在我的实际工作中,元素定位代码的封装较深,所以修改查询元素的内容较麻烦,所以直接使用Xpath Helper可以方便...

    zx钟

扫码关注云+社区

领取腾讯云代金券