数据结构和算法16 之堆排序-阿里云开发者社区

开发者社区> 人工智能> 正文

数据结构和算法16 之堆排序

简介:

   堆排序,顾名思义就是利用堆这个数据结构对数据项进行排序,前面提到过,堆数据结构中,节点大于或等于自己的子节点。那么我们可以将待排序的数据项依次添加到堆中,然后再依次取出根节点即可。从堆中取出的数据项是从大到小排列的。因为根节点永远是最大的,而堆中永远是取根节点。如果对堆这种数据结构不太了解的话,可以先看这篇博文:数据结构和算法之 堆,这里不再赘述。

下面我们来看看堆排序的实现(如果程序有不清楚的地方,也可以参考上面那篇博文)。

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. public class HeapSort {  
  2.     private int[] array;  
  3.     private int currentIndex;  
  4.     private int maxSize;  
  5.     public HeapSort(int size) {  
  6.         maxSize = size;  
  7.         array = new int[maxSize];  
  8.         currentIndex = 0;  
  9.     }  
  10.     //插入数据项,并排好序  
  11.     public void insertSort(int[] source) {  
  12.         for(int i = 0; i < source.length; i++) {  
  13.             array[currentIndex] = source[i]; //插入到节点尾  
  14.             tickedUp(currentIndex++); //向上重新排好序,使得满足堆的条件  
  15.         }  
  16.     }  
  17.     private void tickedUp(int index) {  
  18.         int parentIndex = (index - 1) / 2//父节点的索引  
  19.         int temp = array[index]; //将新加的尾节点存在temp中  
  20.         while(index > 0 && array[parentIndex] < temp) {  
  21.             array[index] = array[parentIndex];  
  22.             index = parentIndex;  
  23.             parentIndex = (index - 1) / 2;  
  24.         }  
  25.         array[index] = temp;  
  26.     }  
  27.       
  28.     //取出最大值  
  29.     public int getMax() {  
  30.         int maxNum = array[0];  
  31.         array[0] = array[--currentIndex];  
  32.         trickleDown(0);  
  33.         return maxNum;  
  34.     }  
  35.     private void trickleDown(int index) {  
  36.         int top = array[index];  
  37.         int largeChildIndex;  
  38.         while(index < currentIndex/2) { //while node has at least one child  
  39.             int leftChildIndex = 2 * index + 1;  
  40.             int rightChildIndex = leftChildIndex + 1;  
  41.             //find larger child  
  42.             if(rightChildIndex < currentIndex &&  //rightChild exists?  
  43.                     array[leftChildIndex] < array[rightChildIndex]) {  
  44.                 largeChildIndex = rightChildIndex;  
  45.             }  
  46.             else {  
  47.                 largeChildIndex = leftChildIndex;  
  48.             }  
  49.             if(top >= array[largeChildIndex]) {  
  50.                 break;  
  51.             }  
  52.             array[index] = array[largeChildIndex];  
  53.             index = largeChildIndex;  
  54.         }  
  55.         array[index] = top;  
  56.     }  
  57. }  

        算法分析:堆中插入和取出的时间复杂度均为O(logN),所以堆排序算法的时间复杂度为O(NlogN),但是堆排序也需要额外的和待排序序列大小相同的存储空间。空间复杂度为O(N)。


转载:http://blog.csdn.net/eson_15/article/details/51193399

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章