写给媳妇儿的算法(三)——选择排序

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

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

算法过程

面对这个问题,我们可以怎么做呢?换做是我的话,我会做这么几个步骤:

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

好了,我会这么办:

  • 1、再找一张 新纸
  • 2、从头到尾查看待办事项列表,找到分数最高的那个事项,写到 新纸 的最开始,并在之前的列表中 划去 这个待办事项。
  • 3、再次从头到尾查看待办事项列表,找到分数最高的事项,写到目前只有一个待办事项的 新纸 上,并在列表中 划去 这个待办事项。

    不断重复2(或者3)的步骤,直到所有旧列表中的事项都被写到了新列表中,这样就得到了一份新的根据重要程度排序得到的待办事项的列表。
写给媳妇儿的算法(三)——选择排序_第1张图片
列表的重新排序过程.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算法解决商旅问题
下一篇: 写给媳妇儿的算法(四)——冒泡排序

你可能感兴趣的