实验代码

# 插入排序递归算法与非递归算法比较
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]
            # 继续往前寻找,如果有比临时变量大的数字,则后移一位,直到找到比临时变量小的元素或者达到列表第一个元素
            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
    # 循环向后加一,直到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(下界,上界,步长)为节省时间选择较大的步长
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()系统模块设置上限值。运行迭代次数在3000以内运行成功大于3000运行失败。
解决办法2：尾递归，每一级调用直接返回函数的返回值更新调用栈,而不用创建新的调用栈, 类似迭代的实现, 时间和空间上均优化了一般递归。
程序逻辑错误

把递归与非递归函数时间统计写在一个函数,最后导致递归算法排序的数组已经被非递归算法排序完成。测试时间如图迭代时间正确,递归在有序数列上排序导致时间几乎不变