Python——关于排序算法（选择排序法）

接前面两篇，今天继续讲选择排序法。

选择排序法（selection sort）

先来看一下百度百科的定义：

选择排序法 是对 定位比较交换法（也就是冒泡排序法） 的一种改进。选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。 简单选择排序的基本思想：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。 百度百科

举个例子：

有列表[3，8，4，2，1，6]

用选择排序法操作：

第一轮：

假设首数字最小，然后依次比对，最终取得最小值的序号，也就是1的序号，然后将1与首位数字互换：

1，8，4，2，3，6

第二轮：

取后方8，4，2，3，6中最小值2，将2与第二位数字互换：

1，2，4，8，3，6

第三轮：

取后方4，8，3，6中最小值3，将2与第三位数字互换：

1，2，3，8，4，6

第四轮：

取后方8，4，6中最小值4，将4与第五位数字互换：

1，2，3，4，8，6

第五轮：

取后方8，6中最小值6，将6与第六位数字互换：

1，2，3，4，6，8

排序完成。

选择排序法总的平均时间复杂度为

。假设列表中的元素是刚好逆序的：比如[6，5，4，3，2，1]那第一轮就要比较5次取得最小值，第二轮4次……1次，总共次数就是1/2*5*（5+1）也就是1/2*（N-1）*N，时间复杂度是n的平方。

coding

#!/usr/bin/env python3.6
# -*- coding: utf-8 -*-
# @Time    : 2019-03-26 19:37
# @Author  : Ed Frey
# @File    : selection_sort.py
# @Software: PyCharm
from time import clock

def timer(f):
    def _f(*args):
        t0 = clock()
        f(*args)
        return clock() - t0
    return _f


def selection_sort(num:list):
    lenth = len(num)
    for j in range(lenth-1):
        pos_min = j
        for i in range(j+1,lenth):
            if num[i]<num[pos_min]:
                pos_min = i
        num[j],num[pos_min] = num[pos_min],num[j]
        print(num)
    return num

if __name__ == '__main__':
    num = [3, 8, 4, 2, 1, 6]

    time = timer(selection_sort)(num)
    print(time)

运行结果如下：

[1, 8, 4, 2, 3, 6]

[1, 2, 4, 8, 3, 6]

[1, 2, 3, 8, 4, 6]

[1, 2, 3, 4, 8, 6]

[1, 2, 3, 4, 6, 8]

5.3999999999998494e-05

小结

到这期为止我们讲了3种常见的排序方法，但是呢，python有自带的内置语法，就是sorted(num:list)和num.sort()，显然这个内置的算法是更更更快的，平时如有用到排序，可别无聊到自己写一个低效的哟。至于为何还要学最底层的排序方法，自然是学习数据结构和算法绕不开的坑，打好基础是关键。

后面两期会更新稍微复杂一点的排序方法，合并排序法，以及快速排序法，敬请期待哦～