堆排序

堆排序：
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

堆：
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

堆排序的基本思想是：
1、将待排序序列构造成一个大顶堆（升序大顶堆，降序小顶堆）
2、此时，整个序列的最大值就是堆顶的根结点
3、将其与末尾元素进行交换，此时末尾就为最大值
4、如何将剩余n-1个元素重写构造成一个堆，这样就会得到n个元素的次小值。
如此反复执行，便能得到一个有序序列

时间复杂度：O(nlogn)
稳定度：不稳定

代码实现

public static void heapSort(int[] arr) {
	//找到第一个非叶子结点 （arr.lentgh / 2 - 1 的索引处就是第一个非叶子结点）
	//排成一个大顶堆
	for(int i = arr.length / 2 - 1; i >= 0; i--){
		adjustHeap(arr, i, arr.length);
	}
	//将顶部和最后一个元素交换位置
	int temp;
	for(int i = arr.length - 1; i > 0; i-- ){
		temp =  arr[i];
		arr[i] = arr[0];
		arr[0] = temp;
		adjustHeap(arr, 0, i);
	}
}

/**
    * 调整为以i为父节点的大顶堆（重点难点）
    * 将一个数组（二叉树），调整成一个大顶堆
    * 举例：int[] arr = {4, 6, 8, 5, 9}; => i = 1 => adjustHeap => 得到{9, 4, 8, 5, 6}
    * 如果再次调用 adjustHeap 传入的是 i = 0 => 得到{4, 9, 8, 5, 6} => {9, 6, 8, 5, 4}
    *
    * @param arr    arr 待调整的数组
    * @param i      i 表示非叶子结点在数组中索引
    * @param length 表示多少个元素继续调整，length 是在追歼的减少
    */
public static void adjustHeap(int[] arr, int i, int length){
	//定义一个临时变量，用于交换
	int temp = arr[i];
	//找到结点i的左子结点，并且每次循环找到k的下一个左子节点
	for(int k = i * 2 + 1; k < length; k = k * 2 + 1){
		//判断左子节点是否小于右子结点，（前提是k+1 必须小于length）
		if(k + 1 < length && arr[k] < arr[k+1]){
			//如果小于，则k++，即k指向右子结点
			k++;
		}
		//当前节点和k结点比较大小
		if(arr[k] > temp) {
			//交换位置
			arr[i] = arr[k];
			//使i指向k，即继续循环 因为交换位置可能会破坏顺序
			i = k; 
		} else {
			break;
		}
	}
	//跳出循环后，我们已经将以 i 为父节点的树的最大值，放在了最顶（局部）
	arr[i] = temp;
}