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

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

相关文章

来自专栏java一日一条

Java 中 Varargs 机制的理解

J2SE 1.5提供了“Varargs”机制。借助这一机制,可以定义能和多个实参相匹配的形参。从而,可以用一种更简单的方式,来传递个数可变的实参。本文介绍这一机...

1003
来自专栏老司机的技术博客

golang学习笔记2:基本结构与数据类型

除了以上介绍的这些关键字,Go 语言还有 36 个预定义标识符,其中包含了基本类型的名称和一些基本的内置函数。

594
来自专栏猿人谷

static用法详解

一. 面向过程程序设计 1、静态全局变量   在全局变量前,加上关键字static,该变量就被定义成为一个静态全局变量。我们先举一个静态全局变量的例子,如下: ...

1809
来自专栏C/C++基础

C++ new的三种面貌

C++中使用new运算符产生一个存在于Heap(堆)上对象时,实际上调用了operator new()函数和placement new()函数。在使用new创建...

741
来自专栏海天一树

小朋友学C语言(19):字符和整数的关系

程序(一) #include <stdio.h> int main() { char ch = 'A'; printf("%c\n", ch);...

3337
来自专栏函数式编程语言及工具

Scalaz(5)- typeclass:my typeclass scalaz style-demo

  我们在上一篇讨论中介绍了一些基本的由scalaz提供的typeclass。这些基本typeclass主要的作用是通过操作符来保证类型安全,也就是在前期编译时...

1869
来自专栏机器学习算法与Python学习

python基础-字符串与编码

转载于:廖雪峰的官方网站-python教程 字符编码 我们已经讲过了,字符串也是一种数据类型,但是,字符串比较特殊的是还有一个编码问题。 因为计算机只能处理数字...

44111
来自专栏java学习

Java每日一练(2017/6/18)

题目要求 本期题目: (单选题) 1、覆盖与重载的关系是( ) A 覆盖只有发生在父类与子类之间,而重载可以发生在同一个类中 B 覆盖方法和重载方法都可以不...

2735
来自专栏码云1024

c++ Struct和Class的区别

2043
来自专栏CDA数据分析师

Python | 十个Python程序员易犯的错误

不管是在学习还是工作过程中,人都会犯错。虽然Python的语法简单、灵活,但也一样存在一些不小的坑,一不小心,初学者和资深Python程序员都有可能会栽跟头。本...

16810

扫码关注云+社区