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

开发者社区> shy丶gril> 正文

数据结构和算法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

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

相关文章
堆排序+代码实现
堆,heap,是二叉树的一种。小根堆有这样的性质——任意一个结点的值比它的左右孩子都要小。 排序思想将待排元素看作是完全二叉树,物理上用一维数组存储。
1021 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
4076 0
排序算法大数据量测试代码
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; using System.Diagnostics; using System.IO; namespace Sort { class Program
813 0
[数据结构]二分插入排序
二分插入排序是对二分查找和插入排序的一个结合,插入操作时通过二分查找找到要插入的位置. #include // 打印数组a void printArr(int a[],int n){ for (int i =...
432 0
【算法导论】堆排序
        堆排序像合并排序一样,时间复杂度为O(nlogn);像插入排序一样,是一种原地排序(在任何时候只有常数个元素存储在数组外)。         二叉堆的概念:是一种数组对象,可以被视为一棵完全二叉树,树的每一层都是填满的,最后一层可能除外。
774 0
算法笔记--堆排序
堆排序也是一种选择排序,对序列的原始顺序不敏感,适用于数据量大的情况。 1. 算法思想           堆:子节点的值总是小于/大于它的父节点。这里使用的是最大堆。           将数组转化为最大堆,依次将对顶元素取出,与堆中最后一个元素交换,堆长度减一,对堆作调整;如此循环至堆为空,最后得到一个元素由小到大排列的数组。
587 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
5735 0
算法与数据结构大系列 - NO.1 - 插入排序
概述 这是一种就地比较排序算法。这里,维护一个始终排序的子列表。例如,维护数组的下半部分以进行排序。要在此已排序的子列表中“插入”的元素必须找到其适当的位置,然后必须将其插入其中。因此名称,插入排序。
1023 0
+关注
1878
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载