每天学习一点儿算法-选择排序

很多算法只有在数据经过排序后才管用，比如我们之前学习的二分查找。当然，很多语言都内置了排序算法，比如Python中的sort()函数和sorted()函数。我们可以直接调用内置函数完成排序，而不需要从头编写。

但是选择排序是快速排序的基石，而快速排序是一种重要的算法。所以，我们有必要对选择排序有一个基本的了解。

在学习选择排序之前，我们先回顾一下Python中的两种基本数据结构：数组和链表。

数组和链表

数组的特点就是：

数组中的每个元素在内存单元中都是连续的

数组的元素从0开始编号，我们可以通过编号立即找到某个元素，因此数组的访问元素速度为O(1)。

链表的特点就是：

链表中的元素可存储在内存的任何地方，每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。

在链表中添加元素很容易，只需将其放入内存，并将其地址存储在前一个元素中，因此链表的插入速度为O(1)

下面来对比一下数组和链表的基本操作的运行时间：

数组可以通过编号随机访问，因此读取速度为O(1)。但在数组中插入（或删除）元素，需要将后面的元素全部后移（或前移）。因此插入（或删除）的速度为O(n)。

链表只能顺序访问，因此读取速度为O(n)。但在链表中插入数据很简单，只需要修改它前面的那个元素指向的地址。因此插入或删除的速度为O(1)。

选择排序

做了这么多的铺垫，其实和选择排序也就只有半毛钱的关系。选择排序的思路很简单：

先找出最大（或最小）的元素放在第一位，其他不变

再找出次大（或次小）的元素放在第二位，其他不变

重复以上步骤，直至所有元素排列完毕

举一个例子（从小到大排序）：

下面贴一个用Python实现的选择排序：

执行结果：

小结

需要存储多个元素时，可用数组或链表

数组的元素时连续的；链表的元素是分开的

数组的读取速度很快；链表的插入和删除速度很快

每天学习一点点，每天进步一点点。