本文目录一览:
c语言 堆排序算法升序排列N个数
#include cstdio
int arr[120000];
int main()
{
int T,n;
scanf("%d",T);
while (T--)
{
scanf("%d",n);
for (int i =1 ; i = n ; i ++)
scanf("%d",arr[i]);
sort(arr+1,arr+n+1);
for (int i = 1; i = n ; i ++)
printf("%d%c",arr[i],i==n?'\n':' ';
}
return 0;
}
C语言堆排序 几个不明白的地方。高手帮忙啊!~
这里为什么是i=n/2-1,初学者可能会不明白。
你这样考虑。
首先对于叶子节点,我们没有必要进行维护操作,也就是没有必要调用你的HeapAdjust
函数
为什么呢?因为叶子节点没有孩子。就算调用了,也不起作用。
所以你应该从n/2-1下标所对应的节点开始,一直维护到0下标对于的节点。
n/2-1是编号最大的非叶子节点,而0号节点是根节点
至于这里为什么是--i,因为这里是自低向上的维护,最后一个维护的必然是根节点。
实际上这两句话的作用是建堆。
for(i=n/2-1;i=0;--i)
HeapAdjust(data,i,n-1);
我画了个草图
C语言堆排序最坏的情况下比较次数最多要多少次?
O(n1og2n)在最坏情况下,冒泡排序所需要的比较次数为n(n-1)//2;简单插入排序所需要的比较次数为n(n-1)/2;希尔排序所需要盼的比较次数为0(n1.5);堆排序所需要的比较次数为0(nlog2n)。