经典排序之 堆排序

简介: Author: bakari  Date: 2012.7.30 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为堆排序。 堆排序是运用二叉树建立的一种排序方式,分为两个阶段,建堆和排序。

Author: bakari  Date: 2012.7.30

排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为堆排序。

堆排序是运用二叉树建立的一种排序方式,分为两个阶段,建堆和排序。

看建堆过程:

 1 /***********************************************  
 2  *  Author:bakari  Date:2012.7.29
 3  *  堆排序
 4  *  中心算法:关注建堆的过程
 5  *  i节点的子孩子节点为 2i+1 和 2i+2;
 6  ***********************************************/
 7 //建立堆的数据结构,此为最大堆
 8 void HeapSort::Build_Heap(int current,int last)
 9 {
10     int child = 2 * current + 1;
11     int temp = HeapList[current];
12     while(child <= last)
13     {
14         
15         if (child < last && HeapList[child] < HeapList[child + 1]) child ++; //找到孩子节点中最大的节点
16         if (temp > HeapList[child]) break;    //当前节点大于他的孩子节点说明满足最大堆的特点直接跳出循环 
17         else
18         {
19             HeapList[current] = HeapList[child];   //否则将当前节点与孩子节点交换
20             current = child;              //将孩子节点替换当前节点
21             child = current * 2 + 1;      //继续在孩子节点中找
22         }
23     }
24     HeapList[current] = temp;
25 }

上面有一处小技巧, i 节点 的子孩子节点为 2 i + 1 和 2 i + 2;这个是建堆的关键,上面算法建立的是最大堆,当然也可以建立最小堆,方法类似。

 

OK,堆一旦建好,就可以进行排序了:

 1 void HeapSort::Heap_Sort()
 2 {
 3     for(int i = (len - 2)/2;i >= 0;i--)
 4         Build_Heap(i,len-1);
 5     for (int i = len -1;i > 0; i--)
 6     {
 7         Swap(0,i);
 8         Build_Heap(0,i-1);
 9     }
10 }
目录
相关文章
|
10月前
【经典排序】插入与希尔排序
【经典排序】插入与希尔排序
52 0
|
算法 搜索推荐 C++
算法基础(一)| 快速排序和归并排序详解
⭐写在前面的话:本系列文章旨在复习算法刷题中常用的基础算法与数据结构,配以详细的图例解释,总结相应的代码模板,同时结合例题以达到最佳的学习效果。本专栏面向算法零基础但有一定的C++基础的学习者。
75 0
|
算法 Java
java进阶- 经典排序(插入排序、冒泡排序、快排(分划交换排序)、直接选择排序、堆排序、合并排序)
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/weixin_40254498/article/details/79205834 业余时间学习java,回顾回顾经典算法。
1289 0
|
算法 JavaScript 人工智能
|
机器学习/深度学习 人工智能
|
机器学习/深度学习 人工智能
|
人工智能 移动开发