级别： ★☆☆☆☆
标签：「算法」「选择排序」「Selection Sort」
作者： MrLiuQ
审校： QiShare团队
本篇将重点介绍选择排序，在讲解选择排序之前，我们先复习一下数组和链表等知识。
一、数组 or 链表?
数组和链表作为常用的存储数据结构，有各自的优势与劣势。
- 数组的优势在于查询速度快。
- 链表的优势在于插入与删除速度快。
下面是两者的时间复杂度：
| / | 数组 | 链表 |
|---|---|---|
| 读取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 删除 | O(n) | O(1) |
为什么呢？
这与数组与链表的存储方式有关。
数组是顺序存储，而链表是链式存储。
- 顺序存储：所存储的内存区域是连续的。
- 链式存储：所存储的内存区域是非连续的。
举个例子：图解一下
因此，当我们所存储的数据经常查询，则选择数组好一些。
如果我们的数据经常被操作，并且数据长度经常发生变化，则选择链表好一些。
关于数组的内存存储还有几个小知识点：
对于不可变数组来说，每一次重新赋值都是一次内存整体迁移，相当于开辟了一块新内存存储数据。
对于可变数组来说，系统会预留内存位置，当可变数组的大小超过这个预留内存大小时，会做整体数据迁移，会迁移到一块更大的预留内存位置。
二、选择排序
我们先来看一下选择排序的算法流程：
解释：
1.每一次循环 找到 未排序队列中的最小值的index。（n次）
2.再与前置位交换，未排序队列元素数-1
3.重复n次，得出最终排序队列。
故时间复杂度 = O(n2)
下面是基于python的实现代码：
- 每一次循环 找到 未排序队列中的最小值的index。（n次）
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
- 再与前置位交换，未排序队列元素数-1。(也可以加入新数组)
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
- 完整示例代码：
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, 2, 10, 6, 4, 7])
工程源码：QiAlgorithms的2-2demo
推荐文章：
iOS Runloop（一）
iOS 常用调试方法：LLDB命令
iOS 常用调试方法：断点
iOS 常用调试方法：静态分析
iOS消息转发
iOS 自定义拖拽式控件：QiDragView
iOS 自定义卡片式控件：QiCardView
iOS Wireshark抓包
iOS Charles抓包
