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

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

相关推荐