折半插入排序.txt

数据结构中的各种各样的排序算法

//折半插入排序 
#include <iostream.h>

void binsertSort(int *a,int s);
void print(int *a,int s);

int main()
{
int size;

cout << "Input the length of array:" ;
cin >> size;

int *array=new int[size+1];
for(int i=1;i<=size;i++)
{
cout << "Input element" << i <<" :" ;
cin >> array[i];
}
cout << "\nBefore Sort:" << endl;
print(array,size);

binsertSort(array,size+1);

cout << "\n After Sort:" << endl;
print(array,size);

return 0;
}

void binsertSort(int *a,int s)
{
for(int i=2;i<s;i++)
{
int low=1,
high=i-1,
mid;
a[0]=a[i];
while(low<=high)
{
mid=(low+high)/2;
if(a[0]<a[mid])
high=mid-1;
else
low=mid+1;
}
for(int j=i-1;j>=high+1;j--)
{
a[j+1]=a[j];
}
a[high+1]=a[0];
}
}

void print(int *a,int s)
{
for(int i=1;i<s+1;i++)
{
cout << a[i] << " ";
}
cout << endl;
}

 
  网 院 机 考 >> 堆 排 序 建 堆  
 
 //堆排序
#include <iostream.h> 
void heapSort(int *a,int s);
void heapAdjust(int *a,int l,int h);//建堆和筛选
void print(int *a,int s); 
int main()
{
int size;

cout << "Input the length of array:" ;
cin >> size;

int *array=new int[size+1];
for(int i=1;i<=size;i++)
{
cout << "Input element" << i <<" :" ;
cin >> array[i];
}
cout << "\nBefore Sort:" << endl;
print(array,size);

heapSort(array,size+1);

cout << "\n After Sort:" << endl;
print(array,size);

return 0;
}

void heapSort(int *a,int s)//堆排序
{
int temp=0;

for(int i=s/2;i>0;i--)//建堆
heapAdjust(a,i,s);
for(int j=s-1;j>1;j--)
{
temp=a[j];
a[j]=a[1];
a[1]=temp;

heapAdjust(a,1,j-1);
}
}

void heapAdjust(int *a,int l,int h)//筛选
{
int temp=a[l];

for(int i=2*l;i<=h;i*=2)//原来i<h
{
if(i<h && a[i]<a[i+1])
i++;
if(temp>a[i])//原来a[l]>=a[i]
break;
a[l]=a[i];
l=i;
}
a[l]=temp;
}

void print(int *a,int s)//打印
{
for(int i=1;i<s+1;i++)
{
cout << a[i] << " ";
}
cout << endl;
}