#define SIZE 10
int array[SIZE]={6,8,7,9,0,1,3,2,5,4};
void Heap_Adjust(int *array,int low,int high){//堆排序调整堆算法
int i=low,j=2*i+1; //应为j=2*i+1，可j=2*i也能正确，奇怪,毕竟下标从0开始
int temp=array[i];
while(j<=high)
{
temp=array[i];
if((j<high)&&(array[j]<array[j+1]))
{
j++;
}
if(temp<array[j])
{
array[i]=array[j];
array[j]=temp;
i=j;
j=2*i+1;
}
else break;
}
}
void Heap_Sort(int *array,int n){//堆排序算法,不稳定 O(n*logn)
int i,temp;
for(i=n/2;i>=0;i--) //不为i>=0,就有问题，如i>0,i>1;i=0时才排跟节点，即a[0]
{
Heap_Adjust(array,i,n);
for(int h=0;h<SIZE;h++)
cout<<" "<<array[h];
cout<<" ad i= "<<i<<endl;
}
for(int i=0;i<SIZE;i++)
cout<<" "<<array[i];
cout<<" init"<<endl;
for(i=n;i>0;i--)
{
temp=array[0];
array[0]=array[i];
array[i]=temp;
Heap_Adjust(array,0,i-1);
for(int k=0;k<SIZE;k++)
cout<<" "<<array[k];
cout<<" i= "<<i<<endl;
}
}
int main(void) {
Heap_Sort(array,9);
for(int i=0;i<SIZE;i++)
cout<<" "<<array[i];
puts("\nHello World!!!");
return EXIT_SUCCESS;
}
|
