《算法图解》第二章笔记与课后练习_选择排序算法

软件环境:Python 3.7.0b4

一、选择排序

# 找出数组中的最小元素
def findSmallest(arr):
  # 存储最小的值
  smallest = arr[0]
  # 存储最小元素的索引
  smallest_index = 0
  for i in range(1, len(arr)):
    if arr[i] < smallest:
      smallest_index = i
      smallest = arr[i]      
  return smallest_index

# 排序算法
def selectionSort(arr):
  newArr = []
  for i in range(len(arr)):
      # 找出数组中最小的元素,并将其加入到新的数组中
      smallest = findSmallest(arr)
      newArr.append(arr.pop(smallest))
  return newArr

二、课后练习

答案(如果有更好的欢迎评论或私信~)

2.1:每天都在列表中添加支出项,但每月只读取支出一次。而数组的读取速度很快,但插入速度慢;链表的读取速度慢,但插入速度快。因为我们执行的插入操作比读取操作多,因此使用链表合适。

2.2:经常要执行插入操作——服务员添加点菜单,而链表的插入速度很快;而且不需要执行查找和随机访问操作(这是数组擅长的),因为厨师总是从队列中取出第一个点菜单。综上所述,使用链表合适。

2.3:有序数组。数组让你能够随机访问从而立即获取数组中间的元素,而使用链表无法这样操作。要获取链表中间的元素,就必须从第一个元素开始,沿链接逐渐找到这个元素。

2.4:数组的插入速度很慢。另外如果要使用二分查找算法来查找用户名,数组必须是有序的,因此每次插入用户名后,都必须对数组进行排序。

2.5:查找时,其速度比数组慢,但比链表快;而在插入时,其速度比数组快,但与链表相当。因此,除了查找速度比数组慢,其他方面并不比链表慢。

三、小结

  • 需要存储多个元素时,可使用数组或链表。
  • 数组的元素都是连在一起的,就像一节节车厢。
  • 链表的元素是分散开的,其中每个元素都存储了下一个元素的地址。
  • 数组的读取速度很快。
  • 链表的插入和删除的速度很快。
  • 在同一个数组中,所有元素的类型都必须相同(都为int、double等)。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

控制对象的创建方式(禁止创建栈对象or堆对象)和创建的数量

我们知道,C++将内存划分为三个逻辑区域:堆、栈和静态存储区。既然如此,我称位于它们之中的对象分别为堆对象,栈对象以及静态对象。通常情况下,对象创建在堆上还是在...

962
来自专栏CRPER折腾记

ES6折腾记- 模板字符串

总体来说,模板字符串的出现了,让我们的字符串拼接写的更加优美了;相当简易实用;但是这货并不是万能的,有部分unicode编码字符会造成编译报错

1113
来自专栏杨熹的专栏

Day 1-Java-imooc-2.变量常量

课程地址:http://www.imooc.com/learn/85 总结图片来自 http://www.imooc.com/article/10535 ? 本...

3695
来自专栏数据结构与算法

32:行程长度编码

32:行程长度编码 总时间限制: 1000ms 内存限制: 65536kB描述 在数据压缩中,一个常用的途径是行程长度压缩。对于一个待压缩的字符串而言,我们可...

3626
来自专栏黑泽君的专栏

Java培训实战教程之Java基础知识精华部分(一)(二)(三)

962
来自专栏老九学堂

初学C语言?先搞懂这些基础知识再谈深度学习吧!

编译程序: 如何把源程序转换成机器能够接受的目标程序,软件工作者编制了一系列的软件.通过这些软件,把用户按规定语法写出的语句一一翻译成二进制的机器指令. 这种具...

1422
来自专栏技术博客

C#项目代码规范

   小菜就是小菜,几个人搞出来的项目,让公司大牛稍微看了下,最后送出了惨不忍睹四个字。命名各种各样,五花八门,大写英文、小写英文、大写拼音、小写拼音、英文和拼...

2634
来自专栏韩伟的专栏

框架设计原则和规范(二)

此文是《.NET:框架设计原则、规范》的读书笔记,本文内容较多,共分九章,将分4天进行推送,今天推送4-5章。 1. 什么是好的框架 2. 框架设计...

3095
来自专栏Java社区

Python 自学步骤(文中有福利)

1824
来自专栏我的技术专栏

细说new与malloc的10点区别

1654

扫码关注云+社区

领取腾讯云代金券