查找和排序(折半查找、二叉插入查找、直接插入排序、折半排序、快速排序、

#include<iostream>
using namespace std;
typedef struct{
int *elem;
int length;
}SSTable;
//折半查找
int Search_Bin(SSTable st,int key)
{
int low=1,high=st.length;
while(low<=high)
{
int mid=(low+high)/2;
if(key==st.elem[mid])
{
cout<<"要查找元素在："<<mid+1<<"处"<<endl;
return 0;
}
else if(key<st.elem[mid])
high=mid-1;
else
low=mid+1;
}
if(low>high)
cout<<"查找元素在表中不存在"<<endl;
return 0;
}
typedef struct BiTNode
{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//二叉查找（包含插入）
int SearchandIn(BiTree &T,int key)
{
if(T==NULL)
{
T=(BiTree)malloc(sizeof(BiTNode));
T->data=key;
T->lchild=T->rchild=NULL;
return false;
}
if(key==T->data)
return true;
else if(key<T->data)
return SearchandIn(T->lchild,key);
else
return SearchandIn(T->rchild,key);
}
#define Maxsize 20
typedef struct
{
int key;
}RedType,*red;
typedef struct
{
RedType r[Maxsize+1];
int length;
}list,heap;
//插入排序
void InsertSort(list &L)
{
for(int i=2;i<L.length;i++)
if(L.r[i].key<L.r[i-1].key)
{
L.r[0].key=L.r[i].key;
L.r[i].key=L.r[i-1].key;
for(int j=i-2;L.r[0].key<L.r[j].key;--j)
L.r[j+1].key=L.r[j].key;
L.r[j+1].key=L.r[0].key;
}
}
//折半插入排序
void BInsertSort(list &L)
{
for(int i=2;i<L.length;i++)
{
L.r[0]=L.r[i];
int low=1,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(int j=i-1;j>=high+1;--j)
L.r[j+1]=L.r[j];
L.r[high+1]=L.r[0];
}
}

int Partition(list &L,int low,int high)
{
int pivotkey=L.r[low].key;
while(low<high)
{
while(low<high&&L.r[high].key>=pivotkey)
--high;
int temp=L.r[low].key;
L.r[low].key=L.r[high].key;
L.r[high].key=temp;
while(low<high&&L.r[low].key<=pivotkey)
++low;
temp=L.r[low].key;
L.r[low].key=L.r[high].key;
L.r[high].key=temp;
}
return low;
}
//快速排序
void QSort(list &L,int low,int high)
{
if(low<high)
{
int pivotloc=Partition(L,low,high);
if((low-1)<((L.length-1)-low))
{
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
else
{
QSort(L,pivotloc+1,high);
QSort(L,low,pivotloc-1);
}
}
}
//选择排序
void SelectSort(list &L)
{
for(int i=1;i<L.length;i++)
{
int min=L.r[i].key;
for(int j=i+1;j<L.length;j++)
{
int k;
if(L.r[j].key<min)
{
min=L.r[j].key;
k=j;
if(i!=k)
{
int temp=L.r[i].key;
L.r[i].key=L.r[k].key;
L.r[k].key=temp;
}
}

}
}
}
//堆排序
void HeapAdjust(heap &H,int s,int m)
{
RedType rc=H.r[s];
for(int j=2*s;j<=
m;j*=2)
{
if(j<m&&(H.r[j].key<H.r[j+1].key))
++j;
if(!(rc.key<H.r[j].key))
break;
H.r[s]=H.r[j];
s=j;
}
H.r[s]=rc;
}

void HeapSort(heap &H)
{
for(int i=H.length/2;i>=1;--i)
HeapAdjust(H,i,H.length);
for(i=H.length-1;i>0;i--)
{
RedType temp=H.r[1];
H.r[1]=H.r[i];
H.r[i]=temp;
HeapAdjust(H,1,i-1);
}
}
//归并排序
void Merge(list L,list &h,int i,int m,int n)
{
for(int j=m+1,k=i;i<=m&&j<=n;++k)
{
if(L.r[i].key<L.r[j].key)
h.r[k]=L.r[i++];
else
h.r[k]=L.r[j++];
}
if(i<=m)
while(k<=n&&i<=m)
{
h.r[k]=L.r[i];
k++;
i++;
}
if(j<=n)
while(k<=n&&j<=n)
{
h.r[k]=L.r[j];
k++;
j++;
}
}
void MSort(list L,list &h,int s,int t)
{
list p;
if(s==t)
h.r[s]=L.r[s];
else
{
int m=(s+t)/2;
MSort(L,p,s,m);
MSort(L,p,m+1,t);
Merge(p,h,s,m,t);
}
}
void MergeSort(list &L)
{
MSort(L,L,1,L.length-1);
}

void showlist(list L)
{
for(int i=1;i<L.length;i++)
cout<<L.r[i].key<<" ";
cout<<endl;
}

void main()
{
SSTable st;
int n;
cout<<"输入表的长度：";
cin>>n;
st.length=n;
cout<<"输入表中元素："<<endl;
st.elem=(int *)malloc(st.length*sizeof(int));
for(int i=0;i<n;i++)
cin>>st.elem[i];
cout<<"输入待查找元素：";
int key;
cin>>key;
cout<<"折半查找："<<endl;
Search_Bin(st,key);
cout<<"二叉排序查找"<<endl;
BiTree T=NULL;
for(i=0;i<st.length;i++)
SearchandIn(T,st.elem[i]);
if(SearchandIn(T,key))
cout<<"查找成功"<<endl;
else
cout<<"查找失败"<<endl;
list L;
cout<<"输入有序表长度："<<endl;
cin>>n;
L.length=n+1;
cout<<"输入有序表元素："<<endl;
for(i=1;i<L.length;i++)
cin>>L.r[i].key;
InsertSort(L);
BInsertSort(L);
QSort(L,1,L.length-1);
SelectSort(L);
HeapSort(L);
MergeSort(L);
showlist(L);
}