堆排序

建立堆的时间复杂度为O(n),随后的排序为O(nlgn)；常用于取前K大/小的应用。

	public void heapSort(int[] arr) {
		if (arr == null || arr.length == 0) {
			return;
		}
		for (int i = arr.length / 2; i >= 0; i--) {
			buildHeap(arr, i, arr.length - 1);
		}
		//将堆进行排序.
		for(int j=arr.length-1;j>=1;j--){
			swap(arr, 0, j);//将堆根交换至末尾
			buildHeap(arr, 0, j-1);
		}
	}
	/**
	 * 建立堆,这里创建的是大根堆.
	 * @param arr
	 * @param from
	 * @param to
	 */
	private void buildHeap(int[] arr, int from, int to) {
		int temp = arr[from];
		for (int next = 2 * from + 1; next <= to; next = 2 * next + 1) {
			if (next < to && arr[next] < arr[next + 1]) {
				next++;
			}
			if (temp < arr[next]) {//大根堆
				arr[from] = arr[next];
				from = next;
			}else{
				break;
			}
		}
		arr[from] = temp;
	}
	/**
	 * 对换数值.
	 * @param arr
	 * @param start
	 * @param next
	 */
	private void swap(int[] arr, int start, int next) {
		arr[start] = arr[start] ^ arr[next];
		arr[next] = arr[next] ^ arr[start];
		arr[start] = arr[start] ^ arr[next];
	}