#include<iostream>
using namespace std;
#define MAXSIZE 20
typedef int KeyType;
typedef struct
{
KeyType key;
}RedType;
typedef struct
{
RedType *r;
int length;
}SqList;
int InitList(SqList &L)
{
L.r= new RedType[MAXSIZE];
if(!L.r) exit(-2);
L.length=0;
return 0;
}
int Build_Sq(SqList &L)
{
int i,n;
cout<<"请输入要建立的顺序表的中元素的个数:"<<endl;
cin>>n;
cout<<"请输入数据:"<<endl;
for(i=0;i<n;i++)
cin>>L.r[i].key;
L.length=n;
return 1;
}
//直接插入排序
void InsertSort(SqList &L)
{
int j,i;
for(i=2;i<=L.length;++i)
if(L.r[i].key<L.r[i-1].key)
{
L.r[0]=L.r[i];
L.r[i]=L.r[i-1];
for( j=i-2;L.r[0].key<L.r[j].key;--j)
L.r[j+1]=L.r[j];
L.r[j+1]=L.r[0];
}
}
//折半插入排序
void BInsertSort(SqList &L)
{
int i,j;
for(i=2;i<=L.length;++i)
{
L.r[0]=L.r[i];
int low=1;
int high=i-1;
while(low<=high)
{
int m=(low+high)/2;
if(L.r[0].key<L.r[m].key)
high=m-1;
else
low=m+1;
}
for(j=i-1;j>=high+1;--j)
L.r[j+1]=L.r[j];
L.r[high+1]=L.r[0];
}
}
//冒泡排序
void BubbleSort(SqList &L)
{
int j,t;
int m=L.length-1;
int flag=1;
while((m>0)&&(flag=1))
{
flag=0;
for(j=1;j<m;j++)
if(L.r[j].key>L.r[j+1].key)
{
flag=1;
t=L.r[j].key;
L.r[j].key=L.r[j+1].key;
L.r[j+1].key=t;
}
--m;
}
}
void Print(SqList &L)
{
for(int i=1;i<=L.length;i++)
{
cout<<L.r[i].key<<" ";
}
}
void main()
{
SqList L;
InitList(L);
Build_Sq(L);
cout<<"直接插入排序为:"<<endl;
InsertSort(L);
Print(L);
cout<<endl;
cout<<"折半插入排序为:"<<endl;
BInsertSort(L);
Print(L);
cout<<endl;
cout<<"冒泡排序为:"<<endl;
BubbleSort(L);
Print(L);
}
using namespace std;
#define MAXSIZE 20
typedef int KeyType;
typedef struct
{
KeyType key;
}RedType;
typedef struct
{
RedType *r;
int length;
}SqList;
int InitList(SqList &L)
{
L.r= new RedType[MAXSIZE];
if(!L.r) exit(-2);
L.length=0;
return 0;
}
int Build_Sq(SqList &L)
{
int i,n;
cout<<"请输入要建立的顺序表的中元素的个数:"<<endl;
cin>>n;
cout<<"请输入数据:"<<endl;
for(i=0;i<n;i++)
cin>>L.r[i].key;
L.length=n;
return 1;
}
//直接插入排序
void InsertSort(SqList &L)
{
int j,i;
for(i=2;i<=L.length;++i)
if(L.r[i].key<L.r[i-1].key)
{
L.r[0]=L.r[i];
L.r[i]=L.r[i-1];
for( j=i-2;L.r[0].key<L.r[j].key;--j)
L.r[j+1]=L.r[j];
L.r[j+1]=L.r[0];
}
}
//折半插入排序
void BInsertSort(SqList &L)
{
int i,j;
for(i=2;i<=L.length;++i)
{
L.r[0]=L.r[i];
int low=1;
int high=i-1;
while(low<=high)
{
int m=(low+high)/2;
if(L.r[0].key<L.r[m].key)
high=m-1;
else
low=m+1;
}
for(j=i-1;j>=high+1;--j)
L.r[j+1]=L.r[j];
L.r[high+1]=L.r[0];
}
}
//冒泡排序
void BubbleSort(SqList &L)
{
int j,t;
int m=L.length-1;
int flag=1;
while((m>0)&&(flag=1))
{
flag=0;
for(j=1;j<m;j++)
if(L.r[j].key>L.r[j+1].key)
{
flag=1;
t=L.r[j].key;
L.r[j].key=L.r[j+1].key;
L.r[j+1].key=t;
}
--m;
}
}
void Print(SqList &L)
{
for(int i=1;i<=L.length;i++)
{
cout<<L.r[i].key<<" ";
}
}
void main()
{
SqList L;
InitList(L);
Build_Sq(L);
cout<<"直接插入排序为:"<<endl;
InsertSort(L);
Print(L);
cout<<endl;
cout<<"折半插入排序为:"<<endl;
BInsertSort(L);
Print(L);
cout<<endl;
cout<<"冒泡排序为:"<<endl;
BubbleSort(L);
Print(L);
}