问题 E: 零基础学C/C++114——直接插入排序
题目描述
编一C程序，该程序可以测试多个测试组，每个测试组它能读入一串整数并对它们进行从小到大直接插入排序，同时输出排序时对这些整数进行比较的总次数（输入整数时，相邻的两个用空格隔开，整数个数<2000）。
输入
第一行先输入测试组数T 然后是T个测试组， 每个测试组先输入整数个数N（2<=n<2000) 然后输入1行，包含N个整数，每2个整数之间用空格隔开
输出
对每个测试组输出2行， 第1行输出比较次数 第2行输出排序后的数，2个数之间用一个空格隔开
样例输入 Copy
1
4
3 2 4 5
样例输出 Copy
3
2 3 4 5
题解
本题考查插入排序，思路是假设前面n个数有序，向内插入一项元素使插入后的数组仍然保持有序。
下面是比较次数的分析 例子：3 2 4 5
对于第一个数3有序 3 2 4 5 将2与3比较 2<3，查找3前面的数，变成 2 3（此时j的下标为-1，j！=i-1） count=1；
第二次4与3比较，4>3 变成2 3 4 count=2；
第三次5与4比较，5>4 变成2 3 4 5 count=3；
插入排序代码可视化网站https://visualgo.net/zh
点击查看代码
#include <stdio.h>
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
int n;
scanf("%d",&n);
int a[n];
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
int count=0;
for(int i=1;i<n;i++)
{
int j
for(j=i-1;j>=0;j--)
{
count++;
if(a[j]<=a[i])
break;
}
if(j!=i-1)//此时j<i，但不清楚有多少项大于m的数在a[i]后面，每次把大于m的数往前移，在a[j+1]处插入，保持升序
{
int temp=a[i];
for(int k=i-1;k>j;k--)
{
a[k+1]=a[k];
}
a[j+1]=temp;//由于上面的j--，可以判断出j+1处放原值
}
}
printf("%d\n",count);
for(int i=0;i<n;i++)
{
printf("%d",a[i]);
if(i<n) printf(" ");
}
printf("\n");
}
return 0;
}