堆积排序可以认为是对直接选择排序法的一种改进。
堆积的定义：具有n个数据元素的序列，当且仅当满足条件 a. ki>=k2i 且 ki>=k2i+1 或者 b.ki<=k2i 且 ki<=k2i+1 时，称序列K为一个堆积，简称堆。有时称满足条件a的堆积为大顶堆积，满足条件b的堆积为小顶堆积。
这里采用大顶堆积。
核心思想：第i趟排序就是将序列的前n-i+1个元素组成的序列转换为一个堆积，然后将堆积的第1个元素与堆积的最后那个元素交换位置。
根据这个思想，堆积排序的过程可以归纳为以下步骤：
1.建立初始堆积
2.交换堆积的第1个元素（即最大元素）与堆积的最后那个元素的位置
3.将移走最大值元素之后的剩余元素组成的序列再转换为一个堆积
4.重复上述过程的第2步和第3步n-1次。
算法中的变量i指出根结点的序号（或者指出某棵子树根结点的序号），变量j指出其左右子树根结点值最大者的序号。
算法如下：
（待完成）
性能：
时间复杂度：O(nlog2n)
空间复杂度：O(1)。
是 不稳定排序方法。
不适于 链表上实现。
堆积排序可以认为是对直接选择排序法的一种改进。 堆积的定义：具有n个数据元素的序列，当且仅当满足条件 a. ki>...
十大排序算法 1.插入排序 2.折半插入排序算法 3.选择排序 4.冒泡排序 5.谢尔排序 6.快速排序 7.堆积...
排序的相关概念 排序的分类 根据在排序过程中带排序的记录是否全部被放置在内存中，排序分为：内排序外排序 1.内排序...
1.排序算法的分类 内排序和外排序概念内排序：指在排序期间数据对象全部存放在内存的排序。外排序：指在排序期间全部对...
根据将排序记录是否全部放置在内存中，将排序分为内排序和外排序，之前讲的都是内排序，这里总结一下，内排序分为四类：插...
根据将排序记录是否全部放置在内存中，将排序分为内排序和外排序，之前讲的都是内排序，这里总结一下，内排序分为四类：插...
常考排序 快速排序 归并排序 归并排序求逆序数对 堆排序 堆排序是指利用堆这种数据结构所设计的一种排序算法。 堆积...
1、概念 2、内排序与外排序 内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录...
排序算法总览 排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过...
排序分为内排序和外排序，区别在于： 内排序：在内存中进行的排序外排序：当参与排序的数据量特别大，一次不能全部读入内...
本文标题：内排序6：堆积排序
本文链接：https://www.haomeiwen.com/subject/zfgsghtx.html
网友评论