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.
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)。