《算法图解》系列笔记（二）—— 选择排序

《算法图解》系列笔记（二）—— 选择排序

内存的工作原理

计算机就像是很多抽屉的集合体，每个抽屉都有地址。 这句话描述的很形象。

再进一步，内存工作主要就是 内存寻址（找空抽屉）、内存传输（放置/拿取雨伞）、存取时间和内存延迟。以上原理性的内容就涉及到底层操作系统级（又是另一个学科体系），这里就不再详述，细节可参考经典的教材《计算机操作系统（第四版）》^[1]。 

数组和链表

• 数组可以通过元素的位置（即索引）来随机取数。而在插入或删除元素时，由于需要移动元素后面的位置，此时效率没有链表高。

• 链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。因此链表可以不用连续的内存空间，它的优势在于插入和删除元素方面。

• 从实现方式上看，文中提到的链表属于单链表，实际还有循环链表，双向链表。

  1. 单链表指的是链表中的元素的指向只能指向链表中的下一个元素或者为空，元素之间不能相互指向。也就是一种线性链表。
  2. 双向链表即是这样一个有序的结点序列，每个链表元素既有指向下一个元素的指针，又有指向前一个元素的指针，其中每个结点都有两种指针。
  3. 循环链表指的是在单向链表和双向链表的基础上，将两种链表的最后一个结点指向第一个结点从而实现循环。

• 常见数组和链表操作的运行时间

--	数组	链表
读取	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

选择排序

选择排序是一种灵巧的算法，但其速度不是很快,其运算时间为O(n*n)。

代码[python]（将数组元素按从小到大的顺序排列）：

①先编写一个用于找到数组中最小元素的函数

②再进行排序

def findSmallest(arr):                    #函数是找到数组中最小的元素smallest = arr[0]smallest_index = 0for i in range(1, len(arr)):if arr[i] < smallest:smallest = arr[i]smallest_index = ireturn smallest_indexdef selectionSort(arr):                   #选择排序函数newArr = []for i in range(len(arr)):smallest = findSmallest(arr)      #用上面的函数找到最小值newArr.append(arr.pop(smallest))return newArr

1. 计算机操作系统（第四版） ．西安电子科技大学出版社[引用日期2016-08-26]. ↩