算法小专栏：选择排序

本篇将重点介绍选择排序，在讲解选择排序之前，我们先复习一下数组和链表等知识。

一、数组 or 链表?

数组和链表作为常用的存储数据结构，有各自的优势与劣势。

• 数组的优势在于查询速度快。
• 链表的优势在于插入与删除速度快。

下面是两者的时间复杂度：

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

为什么呢？
这与数组与链表的存储方式有关。

数组是顺序存储，而链表是链式存储。

• 顺序存储：所存储的内存区域是连续的。
• 链式存储：所存储的内存区域是非连续的。

举个例子：图解一下

因此，当我们所存储的数据经常查询，则选择数组好一些。
如果我们的数据经常被操作，并且数据长度经常发生变化，则选择链表好一些。

关于数组的内存存储还有几个小知识点：

1. 对于不可变数组来说，每一次重新赋值都是一次内存整体迁移，相当于开辟了一块新内存存储数据。

2. 对于可变数组来说，系统会预留内存位置，当可变数组的大小超过这个预留内存大小时，会做整体数据迁移，会迁移到一块更大的预留内存位置。

二、选择排序

我们先来看一下选择排序的算法流程：

解释：
1.每一次循环 找到 未排序队列中的最小值的index。（n次）
2.再与前置位交换，未排序队列元素数-1
3.重复n次，得出最终排序队列。
故时间复杂度 = O(n²)

下面是基于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