数组与链表

• 需要将数据存储到内存时,你请求计算机提供存储空间,计算机给你一个存储地址。需要存储多项数据时,有两种基本方式——数组和链表。
• 使用数组意味着所有待办事项在内存中都是相连的(紧靠在一起的)

• 数组存在的问题：
  你额外请求的位置可能根本用不上,这将浪费内存。你没有使用,别人也用不了。
  待办事项超过10个后,你还得转移。

• 链表的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串在一起。只要有足够的内存空间,就能为链表分配内存。

• 链表存在类似的问题。

  在需要读取链表的最后一个元素时,你不能直接读取,因为你不知道它所处的地址,必须先访问元素#1,从中获取元素#2的地址,再访问元素#2并从中获取元素#3的地址,以此类推,直到访问最后一个元素。需要同时读取所有元素时,链表的效率很高:你读取第一个元素,根据其中的地址再读取第二个元素,以此类推。但如果你需要跳跃,链表的效率真的很低。

• 数组读取效率高，链表读取效率低

  需要随机地读取元素时,数组的效率很高,因为可迅速找到数组的任何元素。
  在链表中,元素并非靠在一起的,你无法迅速计算出第五个元素的内存地址,而必须先访问第一个元素以获取第二个元素的地址,再访问第二个元素以获取第三个元素的地址,以此类推,直到访问第五个元素。

时间复杂度：

数组 链表
读取 O(1) O(n)
插入 O(n) O(1)
结论：
插入元素：用链表好
删除元素：用链表好

选择排序(python实现)

    #!/usr/bin/env python3  
    # -*- coding: utf-8 -*-  
    \"""  
     @desc: selection sort
     @author: Bingo Cai
    \"""

    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):
        newArr = []
        for i in range(len(arr)):
            smallest = findSmallest(arr)
            newArr.append(arr.pop(smallest))
        return newArr

    print(selectionSort([5, 3, 6, 2, 10]))

[笔记]《算法图解》 第二章 选择排序

原文：https://www.cnblogs.com/everfight/p/grokking_algorithms_note_2.html