7-5 简化的插入排序 (15分)

本题要求编写程序，将一个给定的整数插到原本有序的整数序列中，使结果序列仍然有序。
输入格式：

输入在第一行先给出非负整数N（<10）；第二行给出N个从小到大排好顺序的整数；第三行给出一个整数X。
输出格式：

在一行内输出将X插入后仍然从小到大有序的整数序列，每个数字后面有一个空格。
输入样例：

5

1 2 4 5 7

3

输出样例：

1 2 3 4 5 7
在这里插入代码片
```#include <stdio.h>
int main()
{
    int n,m,t,j;
    scanf("%d",&n);
    int a[n+1];//之后会把要插入的数放到原数列的最后一位（放在哪都是可以的，反正要排序）
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&m);
    a[n]=m;
    for(int i=0;i<n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            if(a[i]>a[j])
            {
                t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }
    }
    for(int i=0;i<=n;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

7-120 简化的插入排序（15 分）
本题要求编写程序，将一个给定的整数插到原本有序的整数序列中，使结果序列仍然有序。
输入格式：
输入在第一行先给出非负整数N（$<$10）；第二行给出N个从小到大排好顺序的整数；第三行给出一个整数X。
输出格式：
在一行内输出将X插入后仍然从小到大有序的整数序列，每个数字后面有一个空格。
输入样例：
5
1 2 4 5 7
3
输出样例：
1 2 3 4 5 7
个人感悟：作为一个初学者，方法可能不是最简单的，如果有改进意见，欢迎互相交流！本题先考虑特殊情况，即要插入的数最大或者最小，然后再考虑介于中间的情况。就介于中间的情况来说，我用了另外一个数组。首先需要判断要插入的数按顺序应该排在哪个数的后面，之后把在这个数的后面的数先拷贝到另外一个数组，把要插入的数放入前一个数组，之后再把先前拷贝出去的数组再拷贝回来。
#include<stdio.h>
#include<stdlib.h>
int main()
{
  int n,i,x;
  int a[20],b[20];
  int sign,flag,mark;
  scanf("%d",&n);
  for(i=0;i<n;i++)
  {
    scanf("%d",&a[i]); 
  }
  scanf("%d",&x);
  
  
  for(i=0;i<n;i++)//位于数列末尾的情况
  {
  	flag=0;
    if(x<a[i])
    {
      flag=1;
      break;
    }
  }
  if(flag==0)
  {
    a[n]=x;
  }
  
  
  for(i=0;i<n;i++)//位于数列开头的情况
  {
  	mark=0;
    if(x>a[i])
    {
      mark=1;
      break;
    }
  }
  if(mark==0)
  {
    for(i=0;i<n;i++)
    {
      b[i]=a[i];
    }
    a[0]=x;
    for(i=0;i<n;i++)
    {
      a[i+1]=b[i];
    }
  }
  
  if(flag==1&&mark==1)//介于中间的情况
  {
    for(i=0;i<n-1;i++)
    {
      if(x>a[i]&&x<a[i+1])
      {
        sign=i+1;
      }
    }
    for(i=0;i<n-sign+2;i++)
    {
      b[i]=a[sign+i];
    }
    a[sign]=x;
    for(i=0;i<n;i++)
    {
      a[sign+1+i]=b[i];
    }
  }  
  
  for(i=0;i<n+1;i++)
  {
    printf("%d ",a[i]);
  }
  printf("\n");
  system("pause");
  return 0;
}

简化的插入排序（20 point(s)）




本题要求编写程序，将一个给定的整数插到原本有序的整数序列中，使结果序列仍然有序。

输入格式：

输入在第一行先给出非负整数N（<10）；第二行给出N个从小到大排好顺序的整数；第三行给出一个整数X。

输出格式：

在一行内输出将X插入后仍然从小到大有序的整数序列，每个数字后面有一个空格。

输入样例：

5
1 2 4 5 7
3


输出样例：

1 2 3 4 5 7




 

#include <stdio.h>

int main(){

   int a[100],n,i,m,t=0;
   scanf("%d",&n);
   for(i=0;i<n;i++)
     scanf("%d",&a[i]);
   scanf("%d",&m);
   for(i=n;i>0;i--)
   {
     if(m>=a[i-1])
     {
        a[i]=m;
        t=1;
        break;
     }
     else
        a[i]=a[i-1];
   }
   if(t==0)
    a[0]=m;
   for(i=0;i<n+1;i++)
   printf("%d ",a[i]);
    return 0;
  
}


 

C++ PTA 7-6 简化的插入排序
本题要求编写程序，将一个给定的整数插到原本有序的整数序列中，使结果序列仍然有序。
输入格式：

输入在第一行先给出非负整数N（<10）；第二行给出N个从小到大排好顺序的整数；第三行给出一个整数X。
输出格式：

在一行内输出将X插入后仍然从小到大有序的整数序列，每个数字后面有一个空格。
输入样例：
5
1 2 4 5 7
3

输出样例：
1 2 3 4 5 7 

#include <iostream>
int main() {
	using namespace std;
	int n, i, j, x, a[11];
	cin >> n;
	for (i = 0; i < n; i++)
		cin >> a[i];
	cin >> x;
	i = 0;
	while (a[i] < x && i < n)
		i++;
	for (j = n - 1; j >= i; j--) {
		a[j + 1] = a[j];
	}
	a[i] = x;
	for (i = 0; i < n + 1; i++)
		cout << a[i] << " ";
	return 0;
}