打算用python把所有的排序都寫一遍。不過搞笑地是，才寫了個簡單的選擇排序就遇到了不少問題。選擇排序的基本原理這裡就不講了，可以參考維基百科。
具體思路：
剛開始時按照自已的思路寫的Slect_sorting1()，還停留在剛進大學的水平，主要問題是每次選擇的時候都會交換此時找到的最小值，即產生了不必要的交換次數。
改進算法主要是將數組交換次數降到最低，Slect_sorting2()是中間出錯的一個例子，貼出來有興趣的可以看看，最後寫出來的是Slect_sorting3()。
分析：
這裡分析的是隨機長生一個的長度為10000的數據，使用內置函數profile分析，對於同樣的數據：
Slect_sorting1()函數性能表現：
10004 function calls in 30.091 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 :0(len)
9999 0.738 0.000 0.738 0.000 :0(range)
1 0.004 0.004 0.004 0.004 :0(setprofile)
1 0.000 0.000 30.088 30.088 :1()
1 29.350 29.350 30.088 30.088 SelectSort.py:8(Slect_sorting1)
1 0.000 0.000 30.091 30.091 profile:0(Slect_sorting1(arr))
0 0.000 0.000 profile:0(profiler)
Slect_sorting3()函數性能表現：
10004 function calls in 12.124 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 :0(len)
9999 0.859 0.000 0.859 0.000 :0(range)
1 0.000 0.000 0.000 0.000 :0(setprofile)
1 0.000 0.000 12.124 12.124 :1()
1 11.265 11.265 12.124 12.124 SelectSort.py:31(Slect_sorting3)
1 0.000 0.000 12.124 12.124 profile:0(Slect_sorting3(arr))
0 0.000 0.000 profile:0(profiler)
從上面就很容易看出差距了，修改後算法的運行時間減少了一半以上，另外對於對於profile函數的相關的返回值可參考附錄。
附錄1（代碼）：
'''
Created on 18 Jul 2014
@author: Frank
'''
import random
import profile
def Slect_sorting1(arr):
arr_len = len(arr)
if arr_len < 2:
return arr
for i in range(arr_len-1):
for j in range(i,arr_len):
if arr[j] < arr[i]:
arr[i],arr[j] = arr[j],arr[i]
return arr
def Slect_sorting2(arr):
arr_len = len(arr)
if arr_len < 2:
return arr
for i in range(arr_len-1):
location = i
for j in range(i,arr_len):
if arr[j] < arr[i]:
location = j
if i!=location:
arr[i],arr[location] = arr[location],arr[i]
return arr
def Slect_sorting3(arr):
arr_len = len(arr)
if arr_len < 2:
return arr
for i in range(arr_len-1):
smallest = arr[i]
location = i
for j in range(i,arr_len):
if arr[j] < smallest:
smallest = arr[j]
location = j
if i!=location:
arr[i],arr[location] = arr[location],arr[i]
return arr
#testing
arr = []
for i in range(1,10000):
arr.append(i)
random.shuffle(arr)
profile.run("Slect_sorting1(arr)")
profile.run("Slect_sorting3(arr)")
附錄2（profile函數返回值）：
ncalls 函數的被調用次數
tottime 函數總計運行時間，除去函數中調用的函數運行時間
percall 函數運行一次的平均時間，等於tottime/ncalls
cumtime 函數總計運行時間，含調用的函數運行時間
percall 函數運行一次的平均時間，等於cumtime/ncalls
filename:lineno(function) 函數所在的文件名，函數的行號，函數名
