选择排序是下一章将介绍的快速排序的基石。
内存的工作原理
计算机就像是很多抽屉的集合体, 每个抽屉都有地址。fe0ffeeb 是一个内存单元的地址。
【细抠起来，这个图形有问题：实际上，计算机的内存是一维的，而图形是二维的。】
需要将数据存储到内存时, 你请求计算机提供存储空间, 计算机给你一个存储地址。需要存储多项数据时, 有两种基本方式——数组和链表。但它们并非都适用于所有的情形, 因此知道它们的差别很重要。
数组和链表
数组
数组中所有元素占用连续的内存，所以通过数组首元素地址，可以计算每个元素的地址。元素的位置称为索引，数组的索引从 0 开始，几乎所有的编程语言都从 0 开始对数组元素进行编号。在同一个数组中, 所有元素的类型都必须相同 (都为 int、double 等)。
数组具有以下特点：
知道每个元素的地址，支持随机访问方式；时间复杂度 O(1)
插入元素时，可能导致元素的移动，最坏情况下，会移动所有元素；由于数组需要连续的内存，当前内存可能无法满足元素的存储，需要重新分配内存空间和进行元素的拷贝；插时间复杂度 O(n)
删除元素后, 必须将后面的元素都向前移；时间复杂度 O(n)
链表
链表的每个元素都存储了下一个元素的地址, 从而使一系列随机的内存地址串在一起。链表中的元素可存储在内存的任何地方。只要有足够的内存空间, 就能为链表分配内存。
链表具有以下特点：
支持顺序访问方式，只能从第一个元素开始逐个地读取元素；时间复杂度 O(n)
在链表中添加元素很容易: 只需将其放入内存, 并将其地址存储到前一个元素中；时间复杂度 O(1)
删除元素只需修改前一个元素指向的地址即可；时间复杂度 O(1)
数组和链表还被用来实现其他数据结构，比如散列表等。
选择排序
算法思想：遍历待排序列表, 找出最大或最小的元素，并添加到到新列表的第一个位置；然后找第二大或第二小的元素，依次类推，直到待排序列表里没有元素为止，此时新列表的元素已按降序或升序排列。
选择排序是一种灵巧的算法, 但其速度不是很快。需要的总时间为 O(n × n), 即 O(n2)。
Python 版本：
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
Haskell 版本：
import Data.List (delete)
selectionSort :: Ord a => [a] -> [a]
selectionSort [] = []
selectionSort arr =
let smallest = minimum arr
in smallest : selectionSort (delete smallest arr)
请关注我的公众号哦