首页 > 代码库 > Java与算法之(8) - 堆排序

Java与算法之(8) - 堆排序

堆是一种特殊的完全二叉树,其特点是所有父节点都比子节点要小,或者所有父节点都比字节点要大。前一种称为最小堆,后一种称为最大堆。

比如下面这两个:

技术分享

那么这个特性有什么作用?既然题目是堆排序,那么肯定能用来排序。想要用堆排序首先要创建一个堆,如果对4 3 6 2 7 1 5这七个数字做从小到大排序,需要用这七个数创建一个最大堆,来看代码:

 

[java] view plain copy
 
 print?技术分享技术分享
  1. public class HeapSort {  
  2.   
  3.     private int[] numbers;  
  4.     private int length;  
  5.   
  6.     public HeapSort(int[] numbers) {  
  7.         this.numbers = numbers;  
  8.         this.length = numbers.length;  
  9.     }  
  10.   
  11.     /** 
  12.      * 调整二叉树 
  13.      * 如果父节点编号为x, 那么左子节点的编号是2x, 右子节点的编号是2x+1 
  14.      * 节点编号从1开始, 对应数组中的索引是编号-1 
  15.      * @param nodeId 节点编号, 从1开始 
  16.      */  
  17.     public void adjust(int nodeId) {  
  18.         int swapId;  
  19.         int flag = 0; //是否需要继续向下调整  
  20.         while(nodeId * 2 <= this.length && flag == 0) {  
  21.             //首先判断它和左子节点的关系, 并用swapId记录值较小的节点编号(最大堆是记录较大的)  
  22.             int index = nodeId - 1; //节点对应数组中数字的索引  
  23.             int leftChild = nodeId * 2 - 1; //左子节点对应数组中数字的索引  
  24.             int rightChild = nodeId * 2; //右子节点对应数组中数字的索引  
  25.             if(numbers[index] < numbers[leftChild])  {  
  26.                 swapId = nodeId * 2;  
  27.             } else {  
  28.                 swapId = nodeId;  
  29.             }  
  30.             //如果有右子节点, 再与右子节点比较  
  31.             if(nodeId * 2 + 1 <= this.length) {  
  32.                 if(numbers[swapId - 1] < numbers[rightChild])  
  33.                     swapId = nodeId * 2 + 1;  
  34.             }  
  35.             //如果最小的节点编号不是自己, 说明子节点中有比父节点更小的  
  36.             if(swapId != nodeId) {  
  37.                 swap(swapId, nodeId);  
  38.                 nodeId = swapId;  
  39.             } else {  
  40.                 flag = 1;  
  41.             }  
  42.         }  
  43.     }  
  44.   
  45.     /** 
  46.      * 交换两个节点的值 
  47.      * @param nodeId1 
  48.      * @param nodeId2 
  49.      */  
  50.     public void swap(int nodeId1, int nodeId2) {  
  51.         int t = numbers[nodeId1 - 1];  
  52.         numbers[nodeId1 - 1] = numbers[nodeId2 - 1];  
  53.         numbers[nodeId2 - 1] = t;  
  54.     }  
  55.   
  56.     /** 
  57.      * 创建最大堆 
  58.      */  
  59.     public void createMaxHeap() {  
  60.         //从最后一个非叶节点到第一个节点依次向上调整  
  61.         for(int i = this.length / 2; i >= 1; i--) {  
  62.             adjust(i);  
  63.         }  
  64.     }  
  65.   
  66.     public static void main(String[] args) {  
  67.         int[] numbers = new int[] { 4, 3, 6, 2, 7, 1, 5 };  
  68.         for(int x = 0; x < numbers.length; x++) {  
  69.             System.out.print(numbers[x] + "  ");  
  70.         }  
  71.         System.out.println();  
  72.         HeapSort heap = new HeapSort(numbers);  
  73.         heap.createMaxHeap();  
  74.     }  
  75. }  

对本例中的数列,从this.length / 2到1,共执行了三轮循环。

 

第一轮:

技术分享

第二轮:

技术分享
第三轮:

技术分享

调整完成后,当前的二叉树已经符合最大堆的特性,可以用来从小到大排序。堆排序的原理是,交换堆顶和最后一个节点的数字,即把最大的数字放到数组最后,然后对除了最大数的前n-1个数从新执行调整过程,使其符合最大堆特性。重复以上过程直到堆中只剩下一个数字。

 

[java] view plain copy
 
 print?技术分享技术分享
  1. public void sort() {  
  2.     while(this.length > 1) {  
  3.         swap(1, this.length);  
  4.         this.length--;  
  5.         adjust(1);  
  6.     }  
  7.     for(int x = 0; x < numbers.length; x++) {  
  8.         System.out.print(numbers[x] + "  ");  
  9.     }  
  10. }  

堆排序的时间复杂度和快速排序的平均时间复杂度一样,是O(nlogn)。

Java与算法之(8) - 堆排序