因为fun里面交换的是形参指针,所以不会影响到实参
a b原来是 3 6,所以还是3 6
如果是
int k = *a;
*a = *b;
*b = k;
则是6 3
算法思路: 构造大根堆,每次把大根堆的根节点放入列表中。
方法: 大根堆对应的完全二叉树中,任意一个节点的关键字都大于或等于它的孩子节点的关键字。最小关键字的记录一定是某个叶子节点,每次筛选,把不是大根堆的边成大根堆,把大根堆的根放在列表里。
筛选时,仅仅处理从根节点开始到某个叶子节点的路径上的节点,
n个节点的完全二叉树高度为 log2(n+1) 取上界,所有筛选的时间复杂度为O(log2n),对高度为h的堆一次筛选比较次数最多2(h-1),对n个关键字比较次数不超过4n
堆排序的时间复制度为O(nlogn),k空间复杂度为O(1) ,不稳定的排序
typedef int KeyType;// 关键字的类型
typedef struct{
KeyType key; //关键字项;
int data;
}RecType; //排序的记录类型定义
//筛选代码
void sift(RecType R[],int low ,int high ){
int i=low,j=2*i; //j是i的左孩子。
RecType tmp=R[i]; //现在i就是双亲。放在tmp里
while(j<=high){
if(j<high&R[j].key<R[j+1].key)
j++;//j 指向大的孩子 如果右边孩子大,++ 后 j就是右孩子如果
if(tmp.key<R[j].key){//双亲小
R[i]=R[j]; //j调整到双亲的位置
i=j;
j=2*i //修改i和j 继续向下。
}
else break; //如果双亲大,那么跳出循环。
}//如果中间没有跳出循环,那么到最后自动出来
R[i]=tmp;
}
//堆排序算法
void HeapSort(RecType R[],int n){
int i;RecType tmp;
for(i=n/2;i>=1;i--)//有n个节点,那么最后一个分支节点是 n/2
sift(R,i,n); //建立初始大根堆
for(i=n;i>=2;i--){ //n-1次循环,完成堆排序
tmp = R[1];
R[1]=R[i]; //R[i] 和 R[1] 换位置
R[i]=tmp;
sift(R,1;i-1); //筛选R[1]节点,得到i-1个节点的堆。这样以后R[1]一直是比较大的那个
}
}