Description
插入排序是一种十分常见的排序方法。

其基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，是一种稳定的排序方法。

请你结合数据结构所学知识，实现这种排序方法，并将每一轮的排序结果输出。

Input
第一行输入整数N（1<=n<=100）代表待排序的数据个数。

接下来一行中有N个整数，代表待排序的数据。

Output
第一行输出原始的数据顺序，接下来每一行输出一趟排序的结果（如果顺序没有改变则不输出），直至排序完成，从而实现数据的升序排列。

如果一开始的数据已经有序，则只输出原始数据。

注意，输出的每一个数字后面均带有一个空格。

Sample Input
Copy sample input to clipboard
5
78 24 13 2 99
Sample Output
78 24 13 2 99
24 78 13 2 99
13 24 78 2 99
2 1
3 2
4 78 99
#include <iostream>
using namespace std;
bool IfChange(int* a, int* b, int n){
for (int i = 0;i < n;i++){
if (a[i] != b[i])
return true;
}
return false;
}
void sort(int* a, int* b, int n){
int pos1, pos2;
for (int i = 1;i < n;i++){
pos1 = i;
pos2 = i;
for (int j = 0;j < i;j++){
if (a[i] < a[j]){
pos1 = i;
pos2 = j;
break;
}
}
for (int j = 0;j < pos2;j++)
b[j] = a[j];
b[pos2] = a[pos1];
int pa = pos2;
int pb = pos2+1;
while (pb < n){
if (pa != pos1)
b[pb++] = a[pa++];
else
pa++;
}
if (IfChange(a,b,n)){
for (int j = 0;j < n;j++){
cout << b[j] << ' ';
}
cout << endl;
}
for (int j = 0;j < n;j++){
a[j] = b[j];
}
}
}
int main(){
int n, num;
cin >> n;
int a[n], b[n];
for (int i = 0;i < n;i++){
cin >> a[i];
cout << a[i] << ' ';
}
cout << endl;
sort(a,b,n);
return 0;
}。