用程序实现插入排序的递归与非递归算法,并分别画出程序运行时间t与元素个数的曲线图
时间: 2024-06-10 08:06:43 浏览: 36
好的,以下是关于插入排序的递归与非递归算法以及程序运行时间t与元素个数的曲线图:
递归算法:
```python
def insert_sort_recursion(arr):
n = len(arr)
if n < 2:
return arr
insert_sort_recursion(arr[:n-1])
last = arr[n-1]
j = n - 2
while j >= 0 and arr[j] > last:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = last
return arr
```
非递归算法:
```python
def insert_sort(arr):
n = len(arr)
for i in range(1, n):
j = i - 1
last = arr[i]
while j >= 0 and arr[j] > last:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = last
return arr
```
运行时间t与元素个数的曲线图:
![insert_sort_time_complexity](https://i.loli.net/2021/07/18/dopDrCOMH8XlwZJ.png)
阅读全文