有了前面的知识，你就可以学习第二种算法——选择排序了。要理解本节的内容，你必须熟悉数组、链表和大O表示法。

假设你的计算机存储了很多乐曲。对于每个乐队，你都记录了其作品被播放的次数。

你要将这个列表按播放次数从多到少的顺序排列，从而将你喜欢的乐队排序。该如何做呢？

一种办法是遍历这个列表，找出作品播放次数最多的乐队，并将该乐队添加到一个新列表中。

再次这样做，找出播放次数第二多的乐队。继续这样做，你将得到一个有序列表。

下面从计算机科学的角度出发，看看这需要多长时间。别忘了， O(n)时间意味着查看列表中的每个元素一次。例如，对乐队列表进行简单查找时，意味着每个乐队都要查看一次。

要找出播放次数最多的乐队，必须检查列表中的每个元素。正如你刚才看到的，这需要的时间为O(n)。因此对于这种时间为O(n)的操作，你需要执行n次。

需要的总时间为 O(n × n)，即O(n2)。

排序算法很有用。你现在可以对如下内容进行排序：

• 电话簿中的人名
• 旅行日期
• 电子邮件（从新到旧）

需要检查的元素数越来越少

随着排序的进行，每次需要检查的元素数在逐渐减少，最后一次需要检查的元素都只有一个。既然如此，运行时间怎么还是O(n2)呢？这个问题问得好，这与大O表示法中的常数相关。

第4章将详细解释，这里只简单地说一说。你说得没错，并非每次都需要检查n个元素。第一次需要检查n个元素，但随后检查的元素数依次为n  1, n – 2, …, 2和1。平均每次检查的元素数为1/2 × n， 因此运行时间为O(n × 1/2 × n)。

但大O表示法省略诸如1/2这样的常数（有关这方面的完整讨论，请参阅第4章） ，因此简单地写作O(n × n)或O(n2)。

选择排序是一种灵巧的算法，但其速度不是很快。快速排序是一种更快的排序算法，其运行时间为O(n log 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

def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr

print selectionSort([5,3,6,2,10])