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

软件环境: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 条评论
登录 后参与评论

相关文章

来自专栏杨熹的专栏

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

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

3365
来自专栏灯塔大数据

技术 | Python从零开始系列连载(七)

导读 上一期学习了Python程序的基本控制流程,相信大家都已经熟悉啦,我们这一期就来学习Python特色数据类型(列表)吧! Python特色数据类型(列表)...

34010
来自专栏章鱼的慢慢技术路

《算法图解》第二章笔记与课后练习

17010
来自专栏企鹅号快讯

如何写好python代码

写代码好比画画,好的代码就像一件艺术品,美观、可读性高,让人看着舒服。代码是写给人看的,不是写给机器看的,遵守一定的代码规范很重要,就像写作文需要总分总结构,这...

3867
来自专栏灯塔大数据

技术 | Python从零开始系列连载(二十六)

为了解答大家学习Python时遇到各种常见问题,小灯塔特地整理了一系列从零开始的入门到熟练的系列连载,每周五准时推出,欢迎大家学积极学习转载~

1445
来自专栏程序员互动联盟

【编程基础第九讲】main函数也有参数?

存在问题: main函数我们使用的多关注的少,特别是参数,如何去用? 解决方案: 有C语言初学者朋友不知道怎么应用main函数的参数,其实也不难,只要对C语言...

34213
来自专栏wym

18年暑假多校赛第一场 1002

http://acm.hdu.edu.cn/showproblem.php?pid=6299

791
来自专栏程序员的知识天地

Python基础为重,成就月薪过万

傻瓜式,傻瓜式的你可以直接点开进行下载,但是智能下载这版本,有的人愿意下载别的版本所以就要用到另外的方法

692
来自专栏开发与安全

C++中四种类型转换以及const_cast是否能改变常量的问题

we have four specific casting operators:dynamic_cast, reinterpret_cast, static_c...

20410
来自专栏韩伟的专栏

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

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

2955

扫码关注云+社区