#include<iostream.h>
#include<time.h>
#include<stdlib.h>
#include<string.h>
int array[21];

template<class T>//用二分搜索法插入新元素input
void insert_new()//

{
int middle=(begin+end)/2;
if(a[0]>=input)
{
memmove(a+1,a,sizeof(T)*n);
a[0]=input;
}
else
{
if(a[end]<=input)
{

memmove(a+end+2,a+end+1,sizeof(T)*(n-end-1));
a[end+1]=input;
}
else
{
if(begin<=end)
{
if(a[middle]==input||(end-middle)==1||(middle-begin)==1)
{
memmove(a+middle+1 ,a+middle,sizeof(T)*(n-middle));
a[middle+1]=input;
n++;
}
else
{
if(a[middle]>input)
{
insert_new(a,begin,middle-1,n,input);
}
else
{
if(a[middle]<input)
{
insert_new(a,middle+1,end,n,input);
}
}
}
}
}
}
}

template<class T>//冒泡法从小到大排序数组
void bubble_sort(T*a,int n)
{
T mi=0;
for(int i=n-1;i>=0;i--)
{
for(int k=0;k<i;k++)
{
if(a[k]>a[k+1])
{
mi=a[k];
a[k]=a[k+1];
a[k+1]=mi;
}
}
}
}
inline void arragement(int*a,int n)//输出数组值
{
int count=0;
for(int i=0;i<n;i++)
{
cout<<a<<" ";
count++;
if(count%5==0)
{
cout<<endl;
}
}
cout<<endl;
}

void re_rand(int n,int*ch)//产生随机数组
{
srand((unsigned)time(0));//以当前时间开始产生随机种子
for(int i=0;i<n;i++)
{
ch=rand();//产生随机数并用数组ch存储
}
}

//extern void* memmove(void*,const void*,unsigned int);//函数声明
//void arragement(int*,int);
//void re_rand(int,int*);
void main()
{
int input;
re_rand(20,array);//产生随机数组
cout<<"Output the random arrag:"<<endl;
arragement(array,20);//输出随机生成的数组
bubble_sort(array,20);
cout<<"Output the ranked array:"<<endl;
arragement(array,20);
cout<<"Input an integer:";
cin>>input;
insert_new(array,0,19,20,input);
cout<<"Output the inserted array:"<<endl;
arragement(array,21);

}