《算法图解》读书笔记-2选择排序(数组与链表)
数组和链表
作者：老练的小白
链表：链表中的元素可储存在内存的任何地方，也就是说可以不连续。链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存串在一起。它的优势是插入方面比较快。
补充知识：其实链表分为单链表和双链表（此图出处）。
说出来你可能不信对于链表的介绍就像开玩笑一样的结束了。。。。。。
但是为了加强下印象简单实现个单链表结构，大佬勿喷。。。
class Node(object):
def __init__(self, value=None, next=None):
'''首先需要个节点，包括value和next属性'''
self.value, self.next = value, next
class LinkedList(object):
'''简单的实现下append方法'''
def __init__(self, maxsize=None):
self.maxsize = maxsize #链表最大长度 默认为None表示无限制（只要内存够用）
self.length = 0 #长度
self.root = Node() #定义根节点（链表起始）
self.tailnode = None #尾结点
def __len__(self):
return self.length
def append(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:#首先判断一波链表是否满了
raise Exception("Full")
node = Node(value) #将加入的值 定义成节点
tailnode = self.tailnode #获取到尾结点
if tailnode is None: #判断是否只有root节点
self.root.next = node #如果只有根结点正好 根节点直接指向该值
else:
self.tailnode.next = node #否则尾结点指向该值
self.length += 1
self.tailnode = node #一定要更新尾结点
数组
数组：其实数组相对好理解，就是将一组数据连续存储，数组的元素是带着标号的，地址是互相挨着的。
链表和数组的操作运行时间如下：
##选择排序
问题：假设计算机内存储了许多音乐，并且记录了被播放的次数，需要按照次数进行排序该如何去做？
首先考虑最笨的做法（选择排序）：每次都看一遍所有数据，假设一共有n个数据，需要看n次并且每次看n个数据，由于O(n)表示的是将每个数据看一遍，所以此操作复杂度为O(n2n^2n2)。
# encoding: utf-8
# @Author : NanG
# create on 2020-03-17 08:59
from datetime import datetime
import numpy as np
def findSmallest(arr):
smallest = arr[0] #最小值（也可以最大值）
smallest_index = 0 #最小值索引
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
def selectionSort(arr):
startime = datetime.timestamp(datetime.now())
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
endtime = datetime.timestamp(datetime.now())
return newArr, endtime-startime
def test_selectionSort():
arrs1 = np.random.randint(10, size=100)
test10, time10 = selectionSort(list(arrs1))
print("time100:{}".format( time10))
print(test10)
arrs2 = np.random.randint(10, size=1000)
test100, time100 = selectionSort(list(arrs2))
print("time100:{}".format( time100))
arrs3 = np.random.randint(10, size=10000)
test1000, time1000 = selectionSort(list(arrs3))
print("time10000:{}".format(time1000))
arrs4 = np.random.randint(10, size=100000)
test1000000, time1000000 = selectionSort(list(arrs4))
print("time100000:{}".format(time1000000))
arrs4 = np.random.randint(10, size=1000000)
test1000000, time1000000 = selectionSort(list(arrs4))
print("time1000000:{}".format(time1000000))
if __name__ == '__main__':
test_selectionSort()
本来想用传说中的五点确定图像的方法（初中画图基础），但是1000000的计算了一个多小时还没结束，有些心疼我的小笔记本就没做完。结果如下（建议用pytest进行单测）：
time100:0.0004849433898925781
time1000:0.049310922622680664
time10000:4.410588026046753
time100000:453.7767798900604
time1000000:>1小时
作者：老练的小白
相关文章
Fredrica
2020-11-10
Tallulah
2021-02-10
Xena
2020-07-03
Serafina
2021-03-06
Hea
2020-10-30
Dorothy
2021-01-14
Antonia
2023-07-20
Jacinda
2023-07-20
Rae
2023-07-20
Winola
2023-07-20
Emily
2023-07-20
Grizelda
2023-07-20
Jayne
2023-07-20
Fern
2023-07-20
Gita
2023-07-20
Radinka
2023-07-20
Gella
2023-07-20
Tertia
2023-07-21
Lark
2023-07-21