数列有序!

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

有n(n<=100)个整数，已经按照从小到大顺序排列好，现在另外给一个整数m，请将该数插入到序列中，并使新的序列仍然有序。

Input

输入数据包含多个测试实例，每组数据由两行组成，第一行是n和m，第二行是已经有序的n个数的数列。n和m同时为0表示输入数据的结束，本行不做处理。

Output

对于每个测试实例，输出插入新的元素后的数列。

Sample Input

3 3
1 2 4
0 0

Sample Output

1 2 3 4

此题可以直接插入然后排序，

但是！！！

此题的目的是为了练习按顺序插入，如果那样写就十分偷懒，毫无意义，不如不写。

正确做法如下：

#include <stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
int main()
{int i, j, n, m;while(~scanf("%d %d", &n, &m)){int a[n + 1];int b[n + 1];//定义新数组b，大小比n大1，比a多存一个mmemset(a, 0, sizeof(a));a[n] = 999999;//为了使i = n时不出现越界，使a[n]等于一个很大的数memset(b, 0, sizeof(b));//a和b都清零，并为a[n]赋一个很大的值if(n == 0 && m == 0){break;//如果n和m同时为0表示输入数据的结束}else{for(i = 0; i < n; i++){scanf("%d", &a[i]);//别忘记取地址！！！}if(m <= a[0]){//如果m比a数组第一个数要小，则直接插入放在第一位b[0] = m;//先将m存到b[0]for(i = 0; i < n; i++){b[i + 1] = a[i];//再将数组a中的数存入后面}}else if(m >= a[n - 1]){for(j = 0; j < n; j++){b[j] = a[j];}b[n] = m;}else{for(i = 0; i < n; i++){if(m >= a[i] && m < a[i + 1]){//找出适合m插入的位置for(j = 0; j <= i; j++){b[j] = a[j];}//先插入数组a中小于m的数b[i + 1] = m;//再插入mfor(j = i + 2; j <= n; j++){b[j] = a[j - 1];}//再插入a数组中大于m的数break;//插入后就结束for循环}}}}for(i = 0; i < n + 1; i++){if(i == 0){printf("%d", b[i]);}else{printf(" %d", b[i]);}}printf("\n");}return 0;
}