打算用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