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

2022-01-25 08:29:36

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

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

[java] view plain copy  数据结构和算法16 之堆排序数据结构和算法16 之堆排序
  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

上一篇：WinDbg分析DMP文件方法完全攻略


下一篇：Redis和Lua