堆排序.txt

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

//堆排序
#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;
}