堆排序实现-lintcode

发表于   |   分类于   |  

题目大意

　　http://www.lintcode.com/problem/sort-integers

　　整数排序，这里用堆排序实现。

题目分析

　　使用最大堆，堆排序的思路是按照算法导论中的思路。写了三个方法，第一个是heapify方法，作用是堆化，调用这个方法的前提是，节点i的左右子树都是堆。第二个方法是构建最大堆，从最后一个不是叶子节点开始往前遍历，逐步堆化，最后整棵树就是堆了。第三个方法就是堆排序了。首先先构建最大堆，构建完之后，树根一定是最大的元素，将树根与最后一个元素交换，然后堆的大小减一（最后一个元素不考虑了），然后调用堆化方法，这样树根又成了最大元素，之后再与最后一个元素交换，如此反复。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class Solution {
    
    private void heapify(int[] A, int i, int len) {
    	int left = 2 * i + 1;
    	int right = 2 * i + 2;
    	int largest = i;
    	if(left < len && A[i] < A[left]) {
    		largest = left;
    	}
    	if(right < len && A[largest] < A[right]) {
    		largest = right;
    	}
    	if(largest != i) {
    		int temp = A[i];
    		A[i] = A[largest];
    		A[largest] = temp;
    		heapify(A, largest, len);
    	}
    }
    
    private void buildMaxHeap(int[] A, int len) {
    	for(int i = len / 2; i >= 0; i--) {
    		heapify(A, i, len);
    	}
    }
    
    private void heapSort(int[] A) {
    	int len = A.length;
    	buildMaxHeap(A, len);
    	for(int i = len - 1; i >= 1; i--) {
    		int temp = A[0];
    		A[0] = A[i];
    		A[i] = temp;
    		heapify(A, 0, i);
    	}
    }
    
    public void sortIntegers(int[] A) {
    	heapSort(A);
    }
}

时间复杂度O(n*logn)