数据结构与算法 - 堆排序
2022/3/1 17:24:49
本文主要是介绍数据结构与算法 - 堆排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
堆排序
顾名思义,是利用堆这种数据结构来进行排序的算法。
如果你了解堆这种数据结构,你应该知道堆是一种优先队列,两种实现,最大堆和最小堆,由于我们这里排序按升序排,所以就直接以最大堆来说吧。
我们完全可以把堆(以下全都默认为最大堆)看成一棵完全二叉树,但是位于堆顶的元素总是整棵树的最大值,每个子节点的值都比父节点小,由于堆要时刻保持这样的规则特性,所以一旦堆里面的数据发生变化,我们必须对堆重新进行一次构建。
既然堆顶元素永远都是整棵树中的最大值,那么我们将数据构建成堆后,只需要从堆顶取元素不就好了吗? 第一次取的元素,是否取的就是最大值?取完后把堆重新构建一下,然后再取堆顶的元素,是否取的就是第二大的值? 反复的取,取出来的数据也就是有序的数据。
我们以[ 8,2,5,9,7,3 ]
这组数据来演示。
首先,将数组构建成堆。
既然构建成堆结构了,那么接下来,我们取出堆顶的数据,也就是数组第一个数 9 ,取法是将数组的第一位和最后一位调换,然后将数组的待排序范围 -1。
现在的待排序数据是[ 3,8,5,2,7 ]
,我们继续将待排序数据构建成堆。
取出堆顶数据,这次就是第一位和倒数第二位交换了,因为待排序的边界已经减 1 。
继续构建堆
从堆顶取出来的数据最终形成一个有序列表,重复的步骤就不再赘述了,我们来看一下代码实现。
代码实现
void sort(vector<int>& arr) { int length = arr.size(); buildHeap(arr, length); } void buildHeap(vector<int>& arr, int length) { for(int i = length/2; i >=0; i--) { sink(arr, i, length); } } // 下沉调整 void sink(vector<int>& arr,int index, int length) { int leftChild = 2 * index +1; // 左孩子下标 int rightChild = 2 * index + 2; // 右孩子下标 int present = index; // 要调整的节点下标 // 下沉左边 if(leftChild < length && arr[leftChild] > arr[present]) { present = leftChild; } // 下沉右边 if(rightChild < length && arr[rightChild] > arr[present]) { present = rightChild; } // 如果下标不想等 证明调换过了 if (present != index) { // 交换值 int temp = arr[index]; arr[index] = arr[present]; arr[present] = temp; // 继续下沉 sink(arr, present, length); } }
这篇关于数据结构与算法 - 堆排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)