一道C语言编程题

Question

有一个已摆好序的数组,今输入一个数,要求按原来的排序的规律将它插入数组中

Answer 1

用插入排序法（你的问题是其中的一步）
下面是完整的排序描述和伪代码

题目:
输入:一组数字{a1,a2，…,an}.
输出:从大到小排序的数组.

其实,插入排序法很简单,拿我们平常玩扑克举例.刚开始时,我们手是空的,桌子上放了n张牌.我们要将牌拿起并按从左到右,从大到小的顺序整理好.拿起第一张牌时,因为手里只有一张拍,显然是按顺序排好的.然后再拿起第二张,如果第二张牌比第一张小,那么直接放在第二张的右面;如果第二张比第一张大,把第一张右移一位,然后把第二张放在第一张原来的位置上.如此下去,手中的牌永远是排好顺序的.当拿起第j张时,从右向左比较,如果第j-1张小,则第j-1张右移一位,然后和第j-2张比较,直到找到合适的位置,将第j张牌插入.当桌面上的牌全部都到了手中的时候,那么这副牌也已经按从左到右,从大到小的顺序排好了.

伪代码表述如下:
1. for 1 to length A[j]
2. do key=A[j]
3. //insert A[j] to sorted sequence A[1,2,…,j-1]
4. i=j-1
5. while(i>0 and A[i]<key)
6. A[i+1]=A[i]
7. i=i-1
8. A[i+1]=key

插入排序法的时间代价为O(n^2),是一种比较低级的排序办法.在待排元素较少时可以使用.

有不明白的给我发邮件[email protected]

Answer 2

#include<stdio.h>
#define MAXNUM 6
int main()
{
int a[MAXNUM]={1,3,5,7,9};//这是从小到大排列
int num,i,j;
printf("输入要插入的数:");
scanf("%d",&num);
if(num<a[0]) //插入的数小于第一个,插在最前面
{
for(i=MAXNUM-1;i>0;i--)
a[i]=a[i-1];
a[0]=num;
}
else if(num>=a[MAXNUM-2])//插入的数大于或等于最后一个，插在最后面
a[MAXNUM-1]=num;
else //插入的数大于或等于第一个，小于最后一个，插在中间
{
for(i=0;i<MAXNUM-1;i++)
if(num>=a[i]&&num<a[i+1])
break;
for(j=MAXNUM-1;j>i;j--)
a[j]=a[j-1];
a[++j]=num;

}
for(i=0;i<MAXNUM;i++)
printf("%d ",a[i]);
return 0;
}本回答被提问者采纳

Answer 3

你的数组大小要保证插入新数后不会越界。如果你想保存10个数后，又想插入两个数，那么至少你的数组大小要为13.具体思想是先找到比你要插入的数大的数的位置（假如你是按从小到大排列的话），然后把这个位置以后的数都一次向后挪一位，最后插入你的数，即可。
源程序如下：
#define M 20
#include<stdio.h>
void main()
{int a[M];
int b,n,i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);/*按从下到大的顺序输入n个数，存储在数组中*/
scanf("%d",&b);/*输入你想插入的数*/
for(i=0;i<n;i++)
if(b<a[i]) break;/*找到第一个比b大的数，然后就把b存在它前面,但要在存之前给b腾出来位置才行*/
for（j=n-1;j>=i;j--)
a[j]=a[j+1];/*把比b大的数都往后移一位，然后把b插进去插到数组的第i个位置就行了*/
a[i]=b;
for(i=0;i<=n;i++)
printf("%4d",a[i]);/*把数组里的数从小到大输出来*/
}

Answer 4

// 把value插入到已经按由小到大排序好的含有size个元素的数组array中
// 假设array的内存容量足够大
void insert_value(int* array, int size, int value)
{
int i,j;
for(i=0;i<size;i++) {
if(array[i]>value)
break;
}
for(j=size;j>i;j--) {
array[j] = array[j-1];
}
array[i] = value;
}

Answer 5

用半折法
#include <stdio.h>
/*n为数组长度，a为要插入的元素 */
void insert(int *p, int n,int a)
{
int low = 0;
int high = n-1;
while (low<=high)
{
int mid = (low+high)/2;
if (a<*(p+mid))
{
high = mid-1;
}
else
{
low = mid+1;
}
}
for ( ; n>=low; --n)
{
*(p+n)=*(p+n-1);
}
*(p+low)=a;
}
main()
{
int arr[10]={1,2,4,5,6};
int a=3;
int len=5;
insert(arr,len,a);
for (int i=0; i<6; ++i)
{
printf("%d ",arr[i]);
}
}