大型商城网站建站,网站维护上海,微信电子宣传册制作app,广西桂林十大特产一、堆排序介绍来源百度百科#xff1a;堆排序(Heapsort)是指利用堆积树#xff08;堆#xff09;这种数据结构所设计的一种排序算法#xff0c;它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆#xff0c;是完全二叉树。前面我已经…一、堆排序介绍来源百度百科堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆是完全二叉树。前面我已经有二叉树入门的文章了当时讲解的是二叉查找树那上面所说的完全二叉树是怎么样的一种二叉树呢还有满二叉树又是怎么的一种二叉树呢甚至还有完满二叉树完全二叉树 除了最后一层之外的其他每一层都被完全填充并且所有结点都保持向左对齐。满二叉树除了叶子结点之外的每一个结点都有两个孩子每一层(当然包含最后一层)都被完全填充。完满二叉树除了叶子结点之外的每一个结点都有两个孩子结点。下面用图来说话完全二叉树(Complete Binary Tree)满二叉树(Perfect Binary Tree)完满二叉树(Full Binary Tree)参考资料www.cnblogs.com/idorax/p/64…简单来说堆排序是将数据看成是完全二叉树、根据完全二叉树的特性来进行排序的一种算法最大堆要求节点的元素都要不小于其孩子最小堆要求节点元素都不大于其左右孩子那么处于最大堆的根节点的元素一定是这个堆中的最大值这里我们讨论最大堆当前每个父节点都大于子节点完全二叉树有个特性左边子节点位置 当前父节点的两倍 1右边子节点位置 当前父节点的两倍 2二、堆排序体验现在我们有一个完全二叉树左子树和右子树都符合最大堆--父子但是我们会发现根元素所在的数并不符合明显的是1是小于7的我们就对其进行交换交换完之后我们会发现右子树又不符合了因为右子树变成了这样最后我们将右子数的最大值也交换到右子树的根元素上于是我们第一次的建堆操作就完成了可以发现的是一次堆建立完之后我们的最大值就在了堆的根节点上随后将堆顶最大值和数组最后的元素进行替换我们就完成了一趟排序了。接下来剩下的数不断进行建堆交换就可以完成我们的堆排序了.........建堆交换....建堆交换...建堆交换...建堆交换..三、堆排序代码实现比较当前父节点是否大于子节点如果大于就交换直到一趟建堆完成/*** 建堆** param arrays 看作是完全二叉树* param currentRootNode 当前父节点位置* param size 节点总数*/public static void heapify(int[] arrays, int currentRootNode, int size) {if (currentRootNode size) {//左子树和右字数的位置int left 2 * currentRootNode 1;int right 2 * currentRootNode 2;//把当前父节点位置看成是最大的int max currentRootNode;if (left size) {//如果比当前根元素要大记录它的位置if (arrays[max] arrays[left]) {max left;}}if (right size) {//如果比当前根元素要大记录它的位置if (arrays[max] arrays[right]) {max right;}}//如果最大的不是根元素位置那么就交换if (max ! currentRootNode) {int temp arrays[max];arrays[max] arrays[currentRootNode];arrays[currentRootNode] temp;//继续比较直到完成一次建堆heapify(arrays, max, size);}}}值得注意的是在上面体验堆排序时我们是左子树和右子数都是已经有父子这么一个条件的了。显然一个普通的数组并不能有这种条件(父子)因此我们往往是从数组最后一个元素来进行建堆/*** 完成一次建堆最大值在堆的顶部(根节点)*/public static void maxHeapify(int[] arrays, int size) {// 从数组的尾部开始直到第一个元素(角标为0)for (int i size - 1; i 0; i--) {heapify(arrays, i, size);}}完成第一次建堆之后我们会发现最大值会在数组的首位接下来不断建堆然后让数组最后一位与当前堆顶(数组第一位)进行交换即可排序for (int i 0; i arrays.length; i) {//每次建堆就可以排除一个元素了maxHeapify(arrays, arrays.length - i);//交换int temp arrays[0];arrays[0] arrays[(arrays.length - 1) - i];arrays[(arrays.length - 1) - i] temp;}四、总结堆排序是比其他排序要难一点他用到了完全二叉树这么一个特性来进行排序代码实现上也比其他排序要复杂一点。参考资料www.cnblogs.com/skywang1234…如果文章有错的地方欢迎指正大家互相交流。习惯在微信看技术文章想要获取更多的Java资源的同学可以关注微信公众号:Java3y
