精选聊城做网站的公司,深圳市建设有限公司,淘宝开网店怎么运营,百度最新版下载一、堆排序的思想 堆排序(Heapsort)是指利用堆积树#xff08;堆#xff09;这种数据结构所设计的一种排序算法#xff0c;它是选择排序的一种。它是通过堆#xff08;若不清楚什么是堆#xff0c;可以看我前面的文章#xff0c;有详细阐述#xff09;来进行选择数据堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆若不清楚什么是堆可以看我前面的文章有详细阐述来进行选择数据通过向下调整算法从第一个非叶子结点开始在局部先创建出大堆或小堆然后父亲结点不断往上走直到整棵树都建成一个堆。 需要注意的是排升序要建大堆排降序建小堆。 然后不断交换根节点和最后一个节点的值交换完后节点的数目减1因为最后一个节点已经是它应该在的位置了不用再参与建堆再从根节点向下建堆除最后一个节点其它节点又会建成一个堆 。 然后重复红色括号中的过程堆排序就完成了。 二、堆排序的图解
下图以建大堆为例排一个升序序列 三、堆排序的实现
3.1向下调整算法的实现
实现堆排序最重要的就是实现向下调整算法。以下是向下调整算法的代码以及解释
//这里以建大堆为例
void AdjustDown(int* a, int n, int root)
{int child root * 2 1;//找到根节点的左孩子while (child n)//判断左孩子是否出界{if (child 1 n a[child 1] a[child])//child 1 n判断右孩子是否出界//a[child 1] a[child]判断左右孩子的大小取左右孩子中大的那一个child;if (a[child] a[root])//入过孩子的值比父亲的值大就交换孩子和父亲的位置Swap(a[child], a[root]);else//如果孩子的值不比父亲的值大就证明大堆已经建好了因为此时父亲的左右子树都是大堆//直接break跳出循环。break;//没有break来到这里就顺着子树继续往下走root child;child root * 2 1;}
}
3.2堆排序的实现
以下是堆排序的代码实现以及解释
void HeapSort(int* a, int n)
{//向下调整建堆for (int i (n - 1 - 1) / 2; i 0; i--){//(n - 1 - 1) / 2找到第一个非叶子节点从第一个非叶子结点开始向下建堆AdjustDown(a, n, i);}//堆建好了int end n - 1;while (end 0){//假设是建大堆将下标为0的元素和下标为end的元素交换//最大的数就排到最后了也就相当于最后的那个数已经排好了不用再参与下面的向下建堆Swap(a[0], a[end]);AdjustDown(a, end, 0);//还没有排好的数向下建堆从0位置开始向下建堆end--;}
}
四、总结
堆排序的时间复杂度为 O(N*logN) 向下建堆时间复杂度为O(N)排序时间复杂度为O(N*logN) 空间复杂度O(1) 稳定性不稳定。
