选择排序算法及其性能分析

打算用python把所有的排序都写一遍。不过搞笑地是，才写了个简单的选择排序就遇到了不少问题。选择排序的基本原理这里就不讲了，可以参考维基百科。具体思路：刚开始时按照自已的思路写的Slect_sorting1（），还停留在刚进大学的水平，主要问题是每次选择的时候都会交换此时找到的最小值，即产生了不必要的交换次数。改进算法主要是将数组交换次数降到最低，Slect_sorting2（）是中间出错的一个例子，贴出来有兴趣的可以看看，最后写出来的是Slect_sorting3（）。分析：这里分析的是随机长生一个的长度为10000的数据，使用内置函数profile分析，对于同样的数据：Slect_sorting1（）函数性能表现： 10004 function calls in 30.091 secondsOrdered by: standard namencalls 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 secondsOrdered by: standard namencalls 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 arrdef 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 arrdef 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/ncallscumtime 函数总计运行时间，含调用的函数运行时间percall 函数运行一次的平均时间，等于cumtime/ncallsfilename:lineno（function）函数所在的文件名，函数的行号，函数名本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-08/134083.htm