堆排序（java）

介绍

1. 建立大顶堆
2. 然后将堆的根节点取出(一般是与最后一个节点进行交换)
3. 再将前length-1个数组重新建立大顶堆。不断重复

构建大顶堆图解

图是我用word画的，画的不好见谅

1.首先得到一个完全二叉树

2.选中第i/2个数

3.把此数与两个孩子作对比并将最大的数字放在此位置

4.然后不断向前寻找直到顶部

将根节点取出与最后一个数交换

最后将前length-1个数重新构建大顶堆不断循环

代码

 
/***
	  * 堆排序O(n*lgn)
	  * @param data
	  * @param i
	  * @param j
	  */
	 public static void swap(int[] data, int i, int j) {  
	        if (i == j) {  
	            return;  
	        }  
	        data[i] = data[i] + data[j];  
	        data[j] = data[i] - data[j];  
	        data[i] = data[i] - data[j];  
	    }  
	  
	    public  int[] heapSort(int[] data) {  
	        for (int i = 0; i < data.length; i++) { createMaxdHeap(data, data.length - 1 - i); swap(data, 0, data.length - 1 - i); // print(data); } return data; } public static void createMaxdHeap(int[] data, int lastIndex) { for (int i = (lastIndex - 1) / 2; i >= 0; i--) {  
	            // 保存当前正在判断的节点  
	            int k = i;  
	            // 若当前节点的子节点存在  
	            while (2 * k + 1 <= lastIndex) {  
	                // biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点  
	                int biggerIndex = 2 * k + 1;  
	                if (biggerIndex < lastIndex) {  
	                    // 若右子节点存在，如果不存在此时biggerIndex应该等于 lastIndex  
	                    if (data[biggerIndex] < data[biggerIndex + 1]) {  
	                        // 若右子节点值比左子节点值大，则biggerIndex记录的是右子节点的值  
	                        biggerIndex++;  
	                    }  
	                }  
	                if (data[k] < data[biggerIndex]) {  
	                    // 若当前节点值比子节点最大值小，则交换2者得值，交换后将biggerIndex值赋值给k  
	                    swap(data, k, biggerIndex);  
	                    k = biggerIndex;  
	                } else {  
	                    break;  
	                }  
	            }  
	        }  
	    }