歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

選擇排序算法及其性能分析

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

Copyright © Linux教程網 All Rights Reserved