【引言】如果把你所有的待办事项都加上一个重要值，比如：1 ~ 100 。最重要的事情100分，最不重要的事情1分，你在添加待办事项的时候，往往是出现一个事项，打上分写进列表（杂乱无序的）。当你想整理这个列表，根据分数高低让最重要的事情排在最开始，最不重要的事情排到最后，你会怎么去排列呢？

选择排序是一种比较简单，但是效率并不高的排序方式，它依次选择每次最大（最小）的，直到所有的项目都被选择完毕。

算法过程

面对这个问题，我们可以怎么做呢？换做是我的话，我会做这么几个步骤：

• 1、再找一张纸。
• 2、拿起一支笔。
  ...

好了，我会这么办：

• 1、再找一张 新纸。
• 2、从头到尾查看待办事项列表，找到分数最高的那个事项，写到 新纸 的最开始，并在之前的列表中 划去 这个待办事项。
• 3、再次从头到尾查看待办事项列表，找到分数最高的事项，写到目前只有一个待办事项的 新纸 上，并在列表中 划去 这个待办事项。
  …
  不断重复2（或者3）的步骤，直到所有旧列表中的事项都被写到了新列表中，这样就得到了一份新的根据重要程度排序得到的待办事项的列表。

列表的重新排序过程.png

这个算法就是 选择排序，因为我们每次都选择当前列表中的最大值，把它写到新的列表并从旧的列表删除。每次的选择最优，导致最终的结果是全局的最优。

时间复杂度

🦑每次寻找列表中的最值都需要把列表从头到尾查看一遍，因此，每次需要查看的次数依次为：
第 1 次查看： n
第 2 次查看：n -1
第 3 次查看：n -2
...
第 n 次查看：1
所以，最坏情况下，排序完成所需要的时间是：n + (n-1) + (n-2) + ... + 1 = ? （等差数列求和公式）:

最多需要查看的总次数.png 按照大O表示法，取个极限，当n无限大的时候，整个式子的极限趋近于： 事项无限多的时候最多查看总次数.png

所以选择排序的复杂度为：

选择排序复杂度.png

算法实现

#coding: utf-8

import numpy as np 

# 找到最大的数
def find_max(list):
    max = list[0]
    index = 0
    for i in range(0, len(list)):
        if list[i] > max:
            max = list[i]
            index = i
    return index 

# 选择排序过程
def selection_sort(list):
    new_list = []
    for _ in range(0, len(list)):
        max_index = find_max(list)
        new_list.append(list.pop(max_index))
    return new_list

arr = np.arange(15)
print('Original Data: {}'.format(arr))
np.random.shuffle(arr)
print('Shuffled Data: {}'.format(arr))
print('Sorted Data: {}'.format(selection_sort(arr.tolist())))

结果是：

排序结果.png


上一篇：写给媳妇儿的算法（二）——2-opt算法解决商旅问题
下一篇：写给媳妇儿的算法（四）——冒泡排序