已有一个排好序的序列,输入一个数插入到该序列中,使其仍然保持有序.

#include<stdio.h>

#define N 100 //N的值可以随便给，给多少随便，最好越大越好，防止出现数组溢出的问题

static int i,count=0//声明静态全局变量

static char choice

void main()

{

int arr[N]

do

{

arr[count]=input()//调用输入函数

count++//用来记录用户输入的数的个数，每调用一次input(),count+1

printf("\n是否继续录入：(Y/N)")

fflush(stdin)

choice=getchar()

}while(choice=='y'||choice=='Y')

printf("排序后的数组是：")

sort(arr)//调用排序函数，并将数组的值传给排序函数，数组传值相当于传的是数组中的首位元素在内存中的物理地址

output(arr)//调用输出函数

printf("\n是否要插入新数字(Y/N)")

fflush(stdin)

choice=getchar()

if(choice=='y'||choice=='Y')

{

do

{

into(arr)

printf("\n插入后的数组信息如下：\n")

output(arr)

printf("\n是否要继续插入新数字(Y/N)")

fflush(stdin)

choice=getchar()

}while(choice=='y'||choice=='Y')

}

}

int input()//输入函数

{

int s

printf("请输入第d%个数：",count+1)

scanf("%d",&s)//用户输入的数保临时存在s中

return s//返回s的值

}

void sort(*ptr)//用指针接收来自数组arr的值（指针是指向数组元素在内存中的16Bit的物理地址）

{

int temp,j

for(i=0i<counti++)

{

for(j=0j<count-1j++)

{

if(*(ptr+j)>*(ptr+j+1))

{

temp=*(ptr+j)

*(ptr+j)=*(ptr+j+1)

*(ptr+j+1)=temp

}

}

}

void output(*ptr)

{

for(i=0i<counti++)

printf("%d\t",*(ptr+j))

}

}

int into(*ptr)

{

ptr[count]=input()//ptr[count]保证了每次新插入的数字都排在数组的最后一位

count++

sort()//再调用排序函数对新数组排序，这样就完成了插入的功能

return ptr[count]

}

以上程序你可能不好理解，给你个比较容易理解的：

#include<stdio.h>

#define N 5

void main()

{

int arr[N+1],i,j,k,temp,num

printf("请输入N个数：",N)

for(i=0i<Ni++)

scanf("%d",arr[i])

printf("\n原数组是：")

for(i=0i<Ni++)

printf("%5d",arr[i])

printf("\n")

for(i=0i<Ni++)//循环排序

{

for(j=0j<N-1j++)

{

if(arr[j]>arr[j+1])

{

temp=arr[j]

arr[j]=arr[j+1]

arr[j+1]=temp

}

}

}

printf("排序后的数组为：")

for(i=0i<Ni++)

printf("%5d",arr[i])

printf("请输入要插入的数：")

scanf("%d",&num)

for(i=0i<Ni++)

{

if(num<arr[i])//数组是按照升序排列的，在数组中找到第一个比插入的数字打的元素，将它的下表记录下来，退出循环

i=k

break

}

for(i=Ni>=ki--)//此循环将数组中的从K位置往后的所有元素统一后移一位，将原来k的位置用新插入的数字num代替，从而实现插入功能

{

arr[N]=arr[N-1]

arr[k]=num

}

printf("插入后的数组是：")

for(i=0i<N+1i++)//注意，插入一个数字后，原数组就多出一个元素，循环输入时，也应该考虑到这点

printf("%5d",arr[i])//输入的每个元素占5个字节

}

插入排序：

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本 *** 作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为⊙(㎡)。是稳定的排序方法。

插入算法（insertionsort）把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外，而第二部分就只包含这一个元素。在第一部分排序后，再把这个最后元素插入到此刻已是有序的第一部分里的正确位置中。

包括：直接插入排序，折半插入排序，链表插入排序，Shell排序

交换排序：

所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。选择排序：

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

选择排序是不稳定的排序方法。归并排序：

归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。

在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记录的有序序列。

每一趟归并的时间复杂度为O(n)基数排序：

“基数排序法”（radixsort）则是属于“分配式排序”（distributionsort），基数排序法又称“桶子法”（bucketsort）或binsort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O(nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。

解法

基数排序的方式可以采用LSD（Leastsignificantdigital）或MSD（Mostsignificantdigital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。外排序：

若排序的文件存入外存储器排序过程借助内外存数据交换（或归并）来完成，则称这种排序为外排序。

一般地，外排序的时间由三部分组成：

(1)预处理时间；

(2)内部合并的时间；

(3)外存读/写记录的时间。望参考

---