You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

62 lines
1.1 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

//堆排序
void swap(int& a,int &b)
{
int tmp = a;
a = b;
b = tmp;
}
void siftAdjust(int elem[],int low,int high)
{
for(int f=low,i=2*low+1;i<=high;i=2*i+1)
{
if(i<high && elem[i]<elem[i+1])
{
i++;
}
if(elem[f]>elem[i])
{
break;
}
swap(elem[f],elem[i]);
f = i;
}
}
void heapSort(int elem[],int n)
{
int i;
for(i=(n-2)/2;i>=0;i--)
{
siftAdjust(elem,i,n-1);
}
for(int i=n-1;i>0;i--)
{
swap(elem[0],elem[i]);
siftAdjust(elem,0,i-1);
}
}
int main(void)
{
int n = 10;
int arr[10] = {0};
for(int i=0;i<n;i++)
{
arr[i]=rand()%100;
}
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
heapSort(arr,n);
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}
//复杂度说明: 其中构建初始堆经推导复杂度为o(n)在交换并重建堆的过程中需交换n-1次。而重建堆的过程中根据完全二叉树的性质交换次数为[log2(n-1),log2(n-2),...,1]逐步递减近似为nlogn。所以堆排序时间复杂度一般认为就是o(n*logn)。