堆排序_筛选法建立初始堆

#include<stdio.h>
/*非递增排序*/
 
void swap(int k[], int i, int j)
{
	int temp;
	temp = k[i];
	k[i] = k[j];
	k[j] = temp;
}
 
void Heapadjust(int k[], int s, int n)
{
	int i, temp;
	temp = k[s]; //临时变量存放当前需要调整的双亲结点。
	for(i=2*s;i<=n;i*=2)  //2*s就是它的左孩子 每一次整完就进行下一个双亲结点(i*=2). 就是下一个左孩子为双亲结点。 
	{
		
		if(i< n && k[i]<k[i+1]) //双亲的左孩子和右孩子。如果右孩子比左孩子大的时候，i++; 最多使i指向最大元素的下标。i小于n确定i不是最后一个结点，要是的话，就没必要+1了嘛
		{
			i++;
		}
		if(temp>=k[i]) //如果temp 大于大的那个孩子的话，就可以跳出循环了。  这个调整的从上到下依次减小的堆。
		{
			break; 
		}
		k[s] = k[i]; //如果不是的话，那么双亲就要调整了，双亲等于大的孩子。
		s = i; //双亲的位置放在s里面。这个时候原来双亲的位置应该变换了。 
	}
	k[s] = temp;//把原来的双亲存放到应该属于它的位置。
}
 
void HeapSort(int k[], int n)
{
	int i;
	/*构造大顶堆*/
	for(i=n/2;i>0;i--) //从下往上，从右往左。只要把前0-n/2给调整好了二叉树就建立起来了。 
	{
		Heapadjust(k,i,n); // m:多大的长度  i：当前存放的双亲结点
	}
	for (i=n; i>1; i--)
	{
		swap(k,1,i);//将第一个元素和最后一个元素互换，随后就放在那里了，最后一个元素应该是最小的数字。
		Heapadjust(k,1,i-1); //这个时候只需要将第一个和数到I-1个数重新进行建堆。
	} 
}
 
 
int main()    
{    
    int i,a[10] = {5,6,2,3,7,9,4,1,3};    
    
    HeapSort(a,9);    
 
 
        
    for(i = 1; i<10; i++)    
    {    
        printf("%d\n", a[i]);    
    }    
    return 0;  
}   

堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左孩子和右孩子节点的值。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。

堆排序也是属于选择排序的一种。

每次选择一个关键字需要log2N次比较。时间复杂度是nlog2n

怎么画堆呢？ 很简单 一个个元素的画，而且按照层次来画，步骤如下：

所谓筛选法建立初始堆 一般是建立小顶堆 先将55放在第一个位置，再将63放在第二个位置，由于55比63小成立不用更换次序，再将44放在第三个位置，由于44比55小所以调换次序，现在次序为（44，63，55）再将38放在第四个位置，由于38比63小两者调换位置，又由于38比44小所以将38与44再调换位置得到次序为（38，44，55，63）再将75放在第五个位置，由于75比44大不用更换，将80放在第六个位置，由于80比55大不用更换位置，现在次序为（38，44，55，63，75，80）再将31放在第七个位置，由于31比55小调换位置，31又比38小再调换位置，现在次序为（31，44，38，63，75，80，55）最后将56放到第8个位置，由于56比63小调换位置，56比44大，不用调换位置由此得到次序为（31，44，38，56，75，80，55，63）

堆适合于记录比较多的文件中.

堆排序在最坏的情况下，其时间复杂度也为O(n*log2n)。

堆的空间复杂度： O（1）.