《算法图解》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))