图说 堆排序
2018-06-18 00:07:25来源:未知 阅读 ()
用例:
将一组数据从大到小进行排列 10, 16, 18, 12, 11, 13, 15, 17, 14, 19
size=10
步骤1.根据数组初始化堆中的数据(无序堆)
步骤2.从最后一个根节点( 下标为(size-1-1)/2 )开始往第一个根节点遍历,依次将每个最小子树排好序,建造一个小堆:
步骤3.进行堆排序:将堆数组的首位置和末位置的数据交换,缩小范围 以--size大小的范围将堆顶数据下调,完成建堆
理解了整个思想,我们就来看代码:
先实现一个下调函数用来建堆,并对堆进行调整:(本案例是从大到小进行排序,所以建的是小堆;若是要从小到大进行排序,则要按照大堆思想进行实现,对代码稍微进行改进即可)
//下调 void AdjustDown(int *array, int parent, int size) { int left = parent * 2 + 1; int right = left + 1; while (left < size) { // 比较左右孩子,保证下标left为最小的节点下标 if (right <size && array[right] < array[left]) { left = right; } // 如果父节点大于左右孩子中较小的节点时,就交换这两个节点,要保证两个子节点都大于父节点 if (left<size && array[parent]>array[left]) { // 交换之后还需继续 将相对较大的数循环向下调 swap(array[left], array[parent]); parent = left; left = parent * 2 + 1; right = left + 1; } else { break; } } }
堆排序:按照图说的步骤来写代码,首先要初始化一个堆数组并对它进行排序,之后再一步步将堆顶与有效堆尾数据进行交换,并逐渐缩小堆的size,一组有序的数据就排好了!
//堆排序 int* HeapSort(int *heap, int size) { for (int start = (size - 1 - 1) / 2; start >= 0; start--) { AdjustDown(heap, start, size); } for (int i = size - 1; i >= 0; --i) { swap(heap[0], heap[i]); AdjustDown(heap, 0, i); } return heap; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- 排序汇总 2020-05-05
- 二叉排序树 2020-05-02
- 排序算法之快速排序代码c++ 2020-04-01
- tmp 2020-04-01
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash