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

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

输入格式：

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

输出格式：

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

输入样例：

5 1 2 4 5 7 3

输出样例：

1 2 3 4 5 7

代码在最后，此处是分析（写的很基础） （更新后为两种方法）

（更新后为两种方法）. 方法一思路：定义数组=> 找到插入值的位置=> 将其后面的值转换位置=> 将其插入，输出数组即可。

首先，我们分析这道题，不难发现其在增加一个数后数组的大小发生了变化，所以我们在定义时直接int a【n+1】即可解决.之后，我们遍历数组，将第二行输入的数字赋值到数组a【n+1】中即可。 接着我们就开始进行数据的调换，但把大象装进冰箱的第一步是打开冰箱门，即我们首先要找到x即插入值的位置应该在哪里。所以我们不难想到遍历数组，当其大于a[i]且小于a[i+1],（在此题中，保证了不重复，不会出现相等的情况）则记录下这个i，此为其位置！再找到其位置后，我们可以开始转换吧，采用的思想是将其错位放置，即例如原本为第五个位置的数放置在第六个位置，将第四个位置的数放在第五个位置（顺序可不能反了啊2333）。 那么又会出现一个最大的问题！如何合理安排其转换？理解了思路后，其实实践中，我们就会发现许多问题，比如错位放置的时候，在哪里停止？从哪里开始？ 在数组中，其第一个数从a[0]开始的，所以其开始的顺序是与正常的逻辑有所差异（即差一位）。所以我们先熟悉正常的，常见的，for循环而了解其循环的次数与特性。 1.当我们输入：（以题目中给出的参考输入值为准）for(i=0;i<n;i++)或者for(i=1;i<=n;i++) `` 那么我们会循环n（即n-0）次.由于我们使用的数组为保持一致性，我们还是使用第一种.

2.在此题中，我们需要交换多少次呢？我们原来一共有n个数，后来变为n+1个数，我们从一般情况来看：当满足以下条件时我们可以得到其位置（即i） if(x>a[i]&&x<a[i+1]) 但我们也应注意到（载体给定的数据中）是第3个而且其i=2；此时我们输入的数据中，最后一个是i=n-1；在这里我们使用新的变量j来计数,并实现交换数组。（保持i的不变）在此循环中我们循环了(n-1)-i+1次即在i后面我们有这么多次交换。注意：a[i]不变，a[i+1]最终会进行x的赋值实现插入（被替换）。（此处类比上述1的特性） for(j=n-1;j>i;j- -); 3.最后，我们考虑到将x插入，则一般情况解决，但是其中的特殊情况：比如x最小或最大在最前面或最后一个，则需要单独处理。（评论有指出给定的数字与有序数列中的相同时的bug，已经修复，而且我觉得题意最后要求排列后为有序数列，就不会给出这样的情况（也许是我错了，但最好加上等于号排除这中可能）。感谢提出问题并交流）

真的代码！

#include<stdio.h> int main(){ int n,j,i,t,x; scanf("%d",&n); int a[n+1]; for(i=0;i<n;i++){//input scanf("%d",&a[i]); } scanf("%d",&x); if(x<a[0]){//special min for(j=n-1;j>=0;j--){//有多少个n移多少次！ a[j+1]=a[j]; }a[0]=x; } else if(x>a[n-1])a[n]=x;//special max else for(i=0;i<n;i++){//do if(x>a[i]&&x<=a[i+1]){ for(j=n-1;j>i;j--){ a[j+1]=a[j]; }a[i+1]=x; break; } } for(i=0;i<n+1;i++){//output printf("%d ",a[i]); } return 0; }

方法二的思路：从后向前比较，如果x>最后一个数字a[n-1]那么将a[n]赋值为x即可停止程序；如果x<a[n-1]，那么我们将a[n-1]向后移一位，再继续循环比较。

这样的好处是我们不必再去考虑一些特殊情况的处理更加符合我们的逻辑习惯代码也更为简单

代码如下：

#include<stdio.h> int main(){ int n,j,i,t,x; scanf("%d",&n); if(n==0){ scanf("%d",&x); printf("%d ",x); return 0; } int a[n+1]; for(i=0;i<n;i++){//input scanf("%d",&a[i]); } scanf("%d",&x); // if(x<a[0]){//special min // for(j=n-1;j>=0;j--){//有多少个n移多少次！ // a[j+1]=a[j]; // }a[0]=x; // } // else if(x>a[n-1])a[n]=x;//special max // // else for(i=n-1;i>=0;i--){//do if(x>a[i]){ a[i+1]=x; break;}//找到x的位置并插入了 else a[i+1]=a[i];//没找到，将大的数字向右移一位，继续比较。 if(i==0) a[0]=x; } for(i=0;i<n+1;i++){//output printf("%d ",a[i]); } return 0; }