您也可以将插入排序视为递归算法。为了对A[1:n]进行排序,递归地对子数组A[1:n - 1]进行排序,然后将A[n]插入已排序的子数组A[1:n - 1]中。为这个递归版本的插入排序编写伪代码。给出其最坏情况运行时间的递归式。
时间: 2023-08-31 10:41:36 浏览: 44
### 回答1:
伪代码如下:
1. procedure recursive-insertion-sort(A[1:n])
2. if n > 1
3. recursive-insertion-sort(A[1:n-1])
4. key = A[n]
5. i = n-1
6. while i >= 1 and A[i] > key
7. A[i+1] = A[i]
8. i = i-1
9. A[i+1] = key
最坏情况运行时间的递归式为 T(n) = T(n-1) + O(n),解得 T(n) = O(n^2)。
### 回答2:
伪代码如下所示:
```
Recursive-Insertion-Sort(A, n)
if n > 1
Recursive-Insertion-Sort(A, n-1)
Insert(A[n], A, n-1)
endif
Insert(key, A, n)
i = n-1
while i >= 0 and A[i] > key
A[i+1] = A[i]
i = i - 1
endwhile
A[i+1] = key
```
最坏情况运行时间的递归式为:
```
T(n) = T(n-1) + O(n)
```
其中 `T(n-1)` 表示对子数组 `A[1:n-1]` 进行排序的时间, `O(n)` 表示将 `A[n]` 插入已排序的子数组 `A[1:n-1]` 中的时间。
### 回答3:
伪代码如下所示:
```
RecursionInsertionSort(A, n)
if n > 1 then
RecursionInsertionSort(A, n-1)
key = A[n]
j = n-1
while j > 0 and A[j] > key do
A[j+1] = A[j]
j = j-1
end while
A[j+1] = key
end if
end RecursionInsertionSort
```
上述伪代码是递归版本的插入排序。它首先对子数组 `A[1:n-1]` 进行递归排序,然后将 `A[n]` 插入已排序的子数组 `A[1:n-1]` 中。
最坏情况下,递归版本的插入排序的运行时间可以通过递归式来表示。设递归版本插入排序的最坏情况运行时间为 `T(n)`,当 `n = 1` 时,表示只有一个元素,无需排序,所以 `T(1) = Θ(1)`。当 `n > 1` 时,每次递归需要递归排序 `n-1` 个元素,然后再进行一次 `while` 循环,最坏情况下需要比较和移动 `n-1` 个元素,因此递归式为:
```
T(n) = T(n-1) + (n-1)
= T(n-2) + (n-2) + (n-1)
= T(n-3) + (n-3) + (n-2) + (n-1)
= ...
= T(1) + (1) + (2) + (3) + ... + (n-2) + (n-1)
= Θ(1) + Θ(1+2+3+...+n-2+n-1)
= Θ(n^2)
```
因此,递归版本插入排序的最坏情况运行时间为 `Θ(n^2)`。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)