首页 > 代码库 > 夯实基础——堆排序
夯实基础——堆排序
堆结构:任意的一个父节点大于其子节点。
逻辑结构:二叉树
物理结构:数组
如果从角标0开始
父节点左孩子节点:2*i+1
父节点右孩子节点:2*i+2
最后一个非叶节点:(n-1)/2
如果从角标1开始
父节点左孩子节点:2*i
父节点右孩子节点:2*i+1
最后一个非叶节点:n/2
堆排序分析:
最优时间复杂度:O(nlog2n)
最坏时间复杂度:O(nlog2n)
平均时间复杂度:O(nlog2n)
空间复杂度:O(1)
稳定性:不稳定
堆排序主要分三个函数:
1 调整成堆结构 void HeapAdjust(int *a,int i,int size);
2 构建堆 void BuildHeap(int *a,int size);
3 堆排序 void HeapSort(int *a,int size);
当角标为0,堆排序代码:
//调整堆 void HeapAdjust(int *a,int i,int size) { int lchild=2*i+1;//左孩子节点 int rchild=2*i+2; int max=i;//临时变量 //startNode->(size-1)/2:最后的一个非叶子节点 //选取大于父节点的孩子节点与父节点交换 //寻找前一个非叶子节点 if(i<=(size-1)/2)//非叶子节点 { if(lchild<=size&&a[lchild]>a[max]) { max=lchild; } if(rchild<=size&&a[rchild]>a[max]) { max=rchild; } if(max!=i) { swap(&a[i],&a[max]); HeapAdjust(a,max,size);//避免调整之后以max为父节点的子树不是堆,简称向下调整 } } }
//构建堆 void BuildHeap(int *a,int size) { int i; //从最后一个非叶节点:(size-1)/2到根节点:0 依次向前遍历 for(i=(size-1)/2;i>=0;i--) { HeapAdjust(a,i,size); } }
//堆排序 void HeapSort(int *a,int size) { int i; BuildHeap(a,size);//构建堆 for(i=size;i>=0;i--) { swap(&a[0],&a[i]); HeapAdjust(a,0,i-1);//重新调整堆节点为大顶堆,每次循环将最大值放到堆尾,然后重新构建size:i-1的堆 } }
//交换 void swap(int *a,int *b) { int temp=*a; *a=*b; *b=temp; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。