3085: [CSP-J 2021] 插入排序

插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生，今天 H 老师刚刚在上课的时候讲了插入排序算法。 假设比较两个元素的时间为O(1)，则插入排序可以以O(n^2)的时间复杂度完成长度为n的数组的排序。不妨假设这n个数字分别存储在 a_1, a_2, ,,,, a_n 之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式： 这下面是 C/C++ 的示范代码：

	for (int i = 1; i <= n; i++)  



	    for (int j = i; j >= 2; j--)  



	        if (a[j] < a[j-1]) { int t = a[j-1]; 

            a[j-1] = a[j];
			       a[j] = t;
		}

 这下面是 Pascal 的示范代码： 

	for i:=1 to n do  



	    for j:=i downto 2 do  



	        if a[j]<a[j-1] then  



	            begin t:=a[i]; 

             a[i]:=a[j];
				    a[j]:=t; end;

点击视频讲解

3 4
3 2 1
2 3
1 3 2
2 2
2 3

1
1
2