首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >《算法图解》NOTE 2 数组、链表及选择排序1.数组2.链表3.选择排序法

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

作者头像
billyang916
发布2018-07-09 16:59:17
3530
发布2018-07-09 16:59:17
举报
文章被收录于专栏:python读书笔记python读书笔记

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

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))
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018.05.22 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1.数组
    • 1.1定义
      • 1.2优缺点
        • 1.2.1优点
        • 1.2.2缺点
      • 1.3适用范围
      • 2.链表
        • 2.1定义
          • 2.2优缺点
            • 2.2.1优点
            • 2.2.2缺点
          • 2.3适用范围
          • 3.选择排序法
            • 3.1实现原理
              • 3.2代码实例
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档