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

打算用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)  函数所在的文件名，函数的行号，函数名