做网站应聘平台,上海电子商务网站开发,济南seo培训,公司免费招聘网站1.概念
堆排序是一种树形选择排序#xff0c;是对简单选择排序的有效改进和优化。
堆(heap)#xff0c;这里所说的堆是数据结构中的堆#xff08;对应于算法#xff09;#xff0c;而不是内存模型中的堆#xff08;数据存储形式#xff0c;还比如#xff1a;栈#…1.概念
堆排序是一种树形选择排序是对简单选择排序的有效改进和优化。
堆(heap)这里所说的堆是数据结构中的堆对应于算法而不是内存模型中的堆数据存储形式还比如栈。
堆数据结构是一种特殊的完全二叉树在这棵树中所有父节点都满足大于等于其子节点的堆叫大根堆所有父节点都满足小于等于其子节点的堆叫小根堆。堆虽然是一颗树但是通常存放在一个数组中父节点和孩子节点的父子关系通过数组下标来确定。
由堆的定义可以看出大顶堆的堆顶元素即第一个元素必为最大项大顶堆小顶堆的堆顶元素即第一个元素必为最小项小顶堆。完全二叉树可以很直观地表示堆的结构。堆顶为根其它为左子树、右子树。 2.算法原理
对于要排序为大顶堆的算法来说初始时把要排序的数的序列看作是一棵顺序存储的二叉树调整它们的存储序使之成为一个堆最后堆的根节点的数最大。每一次子排序末尾为n完成后会将根节点与堆的最后一个节点交换。 然后对前面(n-1)个数重新调整使之成为堆。依此类推直到只有两个节点的堆并对它们按照大小条件作交换最后得到有n个节点的有序序列。 从算法描述来看堆排序需要两个过程一是建立堆二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数二是反复调用渗透函数实现排序的函数。 3.步骤:
1从最后一个节点到第一个节点逐次调用将序列构建成大顶堆。
2将根节点与最后一个节点交换然后断开最后一个节点形成更新后的最后一个节点。
3重复第一、二步直到所有节点断开。 4.代码
以下使用Java代码作为示例
/**堆排序总入口函数arr要排序的数组*/public void heapSort(int[] arr) {int len arr.length;//循环建堆for (int i 0; i len - 1; i) {//建堆len-1-i表示从当前末尾最大的元素之前开始排序buildMaxHeap(arr, len - 1 - i);//交换堆顶和最后一个元素swap(arr, 0, len - 1 - i);}}//交换元素private void swap(int[] data, int i, int j) {int tmp data[i];data[i] data[j];data[j] tmp;}//对data数组从0到lastIndex建大顶堆private void buildMaxHeap(int[] data, int lastIndex) {//从lastIndex处节点的父节点非叶子节点索引为(lastIndex - 1) / 2开始直到第一个节点下标为0for (int i (lastIndex - 1) / 2; i 0; i--) {//k保存正在判断的节点int k i;//如果当前k节点的子节点存在k节点的左子节点的索引为2*k1右子节点的索引为2*k2while (2 * k 1 lastIndex) {//k节点的左子节点的索引int biggerIndex 2 * k 1;//如果biggerIndex小于lastIndex即代表的k节点的右子节点的索引为biggerIndex1的节点存在if (biggerIndex lastIndex) {//若果右子节点的值较大则更新左右子节点值更大的对应的索引到biggerIndexif (data[biggerIndex] data[biggerIndex 1]) {//biggerIndex总是记录较大子节点的索引当前即右子节点biggerIndex;}}//如果k节点的值小于其较大的子节点的值则进行交换位置将更大值放到开始if (data[k] data[biggerIndex]) {//交换节点使父节点的值更大swap(data, k, biggerIndex);//将biggerIndex赋予k开始while循环的下一次循环重新保证k节点的值大于其左右子节点的值k biggerIndex;} else {break;}}}}微风不燥阳光正好你就像风一样经过这里愿你停留的片刻温暖舒心。
我是程序员小迷致力于C、C、Java、Kotlin、Android、Shell、JavaScript、TypeScript、Python等编程技术的技巧经验分享若作品对您有帮助请关注、分享、点赞、收藏、在看、喜欢您的支持是我们为您提供帮助的最大动力。
欢迎关注。助您在编程路上越走越好
