《算法图解》NOTE 2 数组、链表及选择排序1.数组2.链表3.选择排序法

这是《算法图解》的第二篇读书笔记,内容主要涉及数组、链表及选择排序。

1.数组

1.1定义

作为一种基础的数据结构,数组指的是n个元素按照索引号依次存放在一个内存区域的数据结构。其中,索引号相邻的元素在内存的位置也是相邻的。

1.2优缺点

1.2.1优点

支持随机访问。即可根据索引号访问与之对应的元素,从而实现快速访问数组中的元素。

1.2.2缺点

(1)删除、插入元素慢。若要删除或插入元素,则需移动制定元素后面的所有元素。 (2)有溢出的可能。数组的内存不足后,需要将整个数组迁移至容量更大的内存中。

1.3适用范围

需要快速访问元素、但对插入、删除元素的速度要求不高的场景。

2.链表

2.1定义

一种基础数据结构,每个元素除了记录自身的值,还会记录下一个元素的内存地址。

2.2优缺点

2.2.1优点

支持快速插入、删除元素。插入、删除元素的操作简单。只需改变特定元素所指向的内存地址,使其指向插入的元素或被删除元素所指向的元素。

2.2.2缺点

不支持快速访问元素,需要从链表的第一个元素,依次访问后续的元素,以找出目标元素。

2.3适用范围

需要快速插入、删除元素,但对查找元素的时效性要求较低的场合。

3.选择排序法

3.1实现原理

遍历其全部元素,找出其最大(最小)的元素。将其从原来的数组中移至新的数据结构中。再从剩余的元素中找出最大(最小)的元素,重复上述移动元素的步骤,直至原来的数据结构中的元素数量为0。

3.2代码实例

#演示选择排序法
import random

#选择数组中最小的元素
def select_smallest(arr):
    value=float('inf')
    idx=None
    for i in range(0,len(arr)):
        if value>arr[i]:
            value=arr[i]
            idx=i
    return idx


#主题函数
def selection_sort(arr):
    #单独处理arr长度为0或为1的情况
    if len(arr)<=1:
        return arr
    sorted_arr=[]
    while arr:
        idx=select_smallest(arr)
        sorted_arr.append(arr.pop(idx))
    return sorted_arr
        
arr=[random.randint(0,10) for i in range(0,10)]
print('original arr',arr)
print('sorted arr',selection_sort(arr))

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java小白

LinkedHashMap的accessOrder

1959
来自专栏xingoo, 一个梦想做发明家的程序员

c++中类长度解析

通常我们定义一个类,它所占的空间有多大呢? 首先我们看一下下面的这个类 class A{ public: void func1(void){ ...

1855
来自专栏风中追风

try,finally中都有return时程序的执行顺序

 在Java中当try、finally语句中包含return语句时,执行情况到底是怎样的,finally中的代码是否执行,大家各有各的说法,刚好今天有个朋友问了...

36915
来自专栏http://www.cnblogs.com

python 反射

通过字符串映射或修改程序运行时的状态、属性、方法, 有以下4个方法: hasattr(obj,name_str) 判断一个对象obj里是否有对应的name...

3779
来自专栏武军超python专栏

2018-7-18pythoh中函数的参数,返回值,变量,和递归

********************************************************************************...

1314
来自专栏尚国

PHP反序列化漏洞

这里你可以看到, 我代码里的类定义为: class F, 这个序列化就是 F, 我定义变量名字是filename, 它这里也是 filename, 我们可以修改...

1022
来自专栏LEo的网络日志

python技巧分享(六)

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

C++模板之隐式实例化、显示实例化、隐式调用、显示调用和模板特化详解

模板的实例化指函数模板(类模板)生成模板函数(模板类)的过程。对于函数模板而言,模板实例化之后,会生成一个真正的函数。而类模板经过实例化之后,只是完成了类的定义...

1622
来自专栏前端儿

大小写互换

  现在给出了一个只包含大小写字母的字符串,不含空格和换行,要求把其中的大写换成小写,小写换成大写,然后输出互换后的字符串。

1262
来自专栏Python专栏

17个案例带你3分钟搞定Linux正则表达式

来源:https://blog.ansheng.me/article/examples-of-linux-regular-expressions

1573

扫码关注云+社区

领取腾讯云代金券