堆排序原理及JAVA实现

选择类排序

• 基本思想：在第i趟的记录序列中选取关键字第i小的记录作为有序序列的第i个记录。
• 关键：如何从剩余的待排序列中找出最大或最小的那个记录。

堆排序是利用堆的性质对记录序列进行排序的一种排序方法。堆排序是选择类排序。

堆的定义

堆是满足下列性质的数列{K0，K1，K2，……，K（n-1）}：

• (1)小根堆：Ki <= K(2i+1)，且Ki <= K(2i+2)（0<=i<=n/2-1）；
• 或者(2)大根堆：Ki >= K(2i+1)，且Ki >= K(2i+2)（0<=i<=n/2-1）；

其中，Ki相当于二叉树的非叶子节点，K(2i+1)是左孩子节点，K(2i+2)是右孩子节点。

若将此数列看成是一颗完全二叉树，则堆是空数列或是满足下列特性的完全二叉树：

1. 其左、右子树分别是堆；
2. 当左、右子树不空时，根结点的值小于（或大于）左、右子树根结点的值。

堆（大根堆）排序基本思想及步骤

基本思想：

1. 建堆：先将待排序序列文件R[0……n-1]构建成一个大根堆，此堆为初始的无序区；
2. 交换：将堆顶记录（无序区的最大记录R[0]）和无序区的最后一个记录R[n-1]交换，无序区记录个数减去1，有序区记录个数加1，由此得到新的无序区R[0……n-2]和有序区R[n-1]；
3. 调整：将当前无序区R[0……n-2]调整为大根堆；
4. 重复交换操作：将堆顶记录和无序区最后一个记录交换，无序区记录个数减去1，有序区记录个数加1；
5. 重复调整操作：将当前无序区调整为大根堆；
6. ……
7. 直到无序区只有一个元素为止。

假设待排序序列为{7， 3， 5， 1， 6}，要将其按升序排序，其堆排序具体过程如下：

步骤一：建初始堆。（升序使用大根堆，降序使用小根堆）

初始的无序序列逻辑及物理存储结构如下：

从最后一个非叶子结点开始，其下标为i = arr.length/2-1 = 1，即从arr[1]处开始，看其左、右孩子结点的值，找出左、右孩子结点中值最大的结点，记住其下标，然后与其父结点交换；然后，从左往右，从下向上，依次进行调整。直到将其调整成大根堆。

步骤二：交换。将堆顶记录和无序区最后一个记录交换。

圈出来的部分就是新的无序区，即需要下次调整为大根堆的部分。此时下标为4的arr[4]就是有序区。

步骤三：调整。将新的无序区调整为大根堆。

从最后一个非叶子结点（新的无序区的最后一个非叶子结点）开始，其下标为i = （arr.length-1）/2-1 = 1，即从arr[1]处开始，看其左、右孩子结点的值，找出左、右孩子结点中值最大的结点，记住其下标，然后与其父结点交换；然后，从左往右，从下向上，依次进行调整。直到将其调整成大根堆。

步骤四：然后重复交换、调整、交换、调整……操作，直到无序区只有一个记录。

圈出来的是新的无序区，是下一次需要调整的新的无序区。

最终的堆排序结果为下图:

此时，堆排序结束。

代码实现：

public class HeapSort {
	
	/**
	 * 调整一个非叶子结点及它的左、右孩子这三个结点为一个大根堆
	 * @param arr
	 * @param i
	 * @param length
	 */
	private static void adjust(int[] arr, int i, int length) {
		//先保存第一个非叶子结点记录
		int temp = arr[i];
		//从左孩子结点开始
		for(int j = 2*i+1; j < length; j = 2*j+1) {
			//有右孩子，且左孩子记录小于右孩子记录
			if(j+1 < length && arr[j] < arr[j+1]) {
				//用j来保存孩子结点中比较大的孩子结点的下标
				j++;
			}
			//用孩子结点中比较大的孩子的记录和父结点记录做比较
			if(temp < arr[j]) {
				//父结点记录保存最大记录
				arr[i] = arr[j];
				//记录孩子结点的下标，要把父结点的记录赋值给该孩子记录
				i = j;
			} else {
				break;
			}
		}
		arr[i] = temp;
	}
	
	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	/**
	 * 大根堆排序
	 * @param arr
	 */
	public static void heapSort(int[] arr) {
		if(null == arr) {
			return;
		}
		/**
		 * 构建大根堆
		 */
		for(int i = arr.length/2-1; i >= 0; i--) {
			adjust(arr, i, arr.length);
		}
		/**
		 * 交换 + 调整
		 */
		for(int i = arr.length-1; i >= 0; i--) {
			//先交换堆顶记录和无序区最后一个记录
			swap(arr, 0, i);
			//调整无序区为大根堆
			adjust(arr, 0, i);
		}
	}
	
	private static void showArr(int[] arr) {
		for(int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
	
	public static void main(String[] args) {
		int[] arr = {7, 3, 5, 1, 6};
		/**
		 * 堆排序
		 */
		heapSort(arr);
		showArr(arr);
	}

}

运行结果：

效率：

时间复杂度：O（nlogn）；

空间复杂度：O（1）；

稳定性：不稳定排序。