[CSP-J 2021] 插入排序

题目描述

插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生，今天 H 老师刚刚在上课的时候讲了插入排序算法。

假设比较两个元素的时间为 $\mathcal O(1)$，则插入排序可以以 $\mathcal O(n^2)$ 的时间复杂度完成长度为 $n$ 的数组的排序。不妨假设这 $n$ 个数字分别存储在 $a_1, a_2, \ldots, a_n$ 之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式：

这下面是 C/C++ 的示范代码：

for (int i = 1; i = 2; j--)
		if (a[j]  | 无 |
| $5 \sim 9$ | $300$ | $300$  | 无  |
| $10 \sim 13$ | $1500$ | $1500$  | 无 |
| $14 \sim 16$ | $8000$ | $8000$  | 保证所有输入的 $a_i,v$ 互不相同 |
| $17 \sim 19$ | $8000$  | $8000$ | 无 |
| $20 \sim 22$ | $8000$ | $2 \times 10^5$ | 保证所有输入的 $a_i,v$ 互不相同 |
| $23 \sim 25$ | $8000$  | $2 \times 10^5$  | 无 |

## 附件下载

[sort.zip](./4493/file/sort.zip?type=additional_file)