實驗代碼
# 插入排序遞歸算法與非遞歸算法比較
import time
from matplotlib import pyplot as plt
import types
import random
import sys
# 設置上限值
sys.setrecursionlimit(100000)
# 產生隨機數組
def random_int_list(start, stop, length):
start, stop = (int(start), int(stop)) if start <= stop else (int(stop), int(start))
length = int(abs(length)) if length else 0
random_list = []
for i in range(length):
random_list.append(random.randint(start, stop))
return random_list
# 直接插入排序非遞歸實現
def InsertSort(myList):
# 獲取列表長度
length = len(myList)
for i in range(1, length):
# 設置當前值前一個元素的標識
j = i - 1
# 如果當前值小于前一個元素,則將當前值作為一個臨時變量存儲,將前一個元素后移一位
if (myList[i] < myList[j]):
temp = myList[i]
myList[i] = myList[j]
# 繼續(xù)往前尋找,如果有比臨時變量大的數字,則后移一位,直到找到比臨時變量小的元素或者達到列表第一個元素
j = j - 1
while j >= 0 and myList[j] > temp:
myList[j + 1] = myList[j]
j = j - 1
# 將臨時變量賦值給合適位置
myList[j + 1] = temp
# 遞歸算法 從前往后不斷遞歸排序
def InsertSortRecursion(array, i=1):
if i >= len(array):
yield array
if array[i - 1] > array[i]:
temp = array[i]
for a in range(0, i):
if temp < array[a]:
# 在array[a]插入temp
array.insert(a, temp)
# 刪除 最后一個
del array[i + 1]
break
# 循環(huán)向后加一,直到i = len(array)
yield InsertSortRecursion(array, i + 1)
# 尾遞歸,破解遞歸限制
def tramp(gen, *args, **kwargs):
g = gen(*args, **kwargs)
while isinstance(g, types.GeneratorType):
g = g.__next__()
return g
# 非遞歸時間序列
timer = []
# 遞歸時間序列
timer_r = []
n = []
# range(下界,上界,步長)為節(jié)省時間選擇較大的步長
for i in range(0, 50000, 5000):
print("i=", i)
n.append(i)
myList = random_int_list(1, 100000, i)
# 計算非遞歸算法時間
start_time = time.time()
InsertSort(myList)
end_time = time.time()
timer1 = end_time - start_time
print("迭代時間", timer1)
timer.append(timer1)
# 打亂上次已經有序的數列
myList = random_int_list(1, 100000, i)
# 計算遞歸算法時間
start_time1 = time.time()
# InsertSortRecursion(myList)
tramp(InsertSortRecursion, myList)
end_time1 = time.time()
timer2 = end_time1 - start_time1
print("遞歸時間",timer2)
timer_r.append(timer2)
# 繪圖
plt.plot(n,timer,n,timer_r)
plt.legend(['iteration', 'recursion'])
plt.xlabel('n')
plt.ylabel('t')
plt.title(' interation and recursion about insert sort ')
plt.show()
實驗結果
插入排序遞歸算法與非遞歸算法比較
錯誤分析
- 越界錯誤
Python3中迭代限制默認次數為1000次以內,導致數據大于1000個是迭代失敗,
解決辦法1:添加sys.setrecursionlimit()系統(tǒng)模塊設置上限值洞斯。運行迭代次數在3000以內運行成功大于3000運行失敗。
解決辦法2：尾遞歸，每一級調用直接返回函數的返回值更新調用棧,而不用創(chuàng)建新的調用棧, 類似迭代的實現, 時間和空間上均優(yōu)化了一般遞歸飞几。 -
程序邏輯錯誤
把遞歸與非遞歸函數時間統(tǒng)計寫在一個函數,最后導致遞歸算法排序的數組已經被非遞歸算法排序完成轧邪。測試時間如圖
迭代時間正確,遞歸在有序數列上排序導致時間幾乎不變
