python用選擇法進行排序_Python——關于排序算法（選擇排序法）

這是奔跑的鍵盤俠的第98篇文章

接前面兩篇，今天繼續講選擇排序法。

選擇排序法（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]

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()，顯然這個内置的算法是更更更快的，平時如有用到排序，可别無聊到自己寫一個低效的喲。至于為何還要學最底層的排序方法，自然是學習資料結構和算法繞不開的坑，打好基礎是關鍵。

後面兩期會更新稍微複雜一點的排序方法，合并排序法，以及快速排序法，敬請期待哦～