1.1选择算法使用场景很基本流程

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

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

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

再次这样做，找出播放次数第二多的乐队。

继续这样做，你将得到一个有序列表。

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

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

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

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

• 电话簿中的人名

• 旅行日期

• 电子邮件（从新到旧）

选择排序是一种灵巧的算法，但其速度不是很快

图片来自算法图解

1.2选择算法的实现

下面我们已python的写法来实现

1第一步我们这边需要找出数组中的最大值或者最小值,这个很简单就不用做过多的复述

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

2第二步使用上面最小数或最大数函数来编写选择排序算法了（python有pop方法是将元素从数组中弹出）

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

3测试上述代码

arr = [12,10,16,11,9,7,123,2312312,1232132,31232131,123213]
print(selectionSort(arr))

4总结：

这与大 O 表示法中的常数相关。第一次需要检查 n 个元素，但随后检查的元素数依次为 n - 1, n – 2, …, 2和1。平均每次检查的元素数为1/2 × n，因此运行时间为 O(n × 1/2 × n)。因此简单地写作 O(n × n) 或 O(n2)。