堆排序

基本介绍

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

堆是具有以下性质的完全二叉树：

每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。

每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。

一般升序采用大顶堆，降序采用小顶堆。

基本思想

将待排序序列构造成一个大顶堆，此时整个序列的最大值就是堆顶的根节点arr[0]。
将其与末尾元素进行交换，此时末尾就为最大值。
然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
反复执行，便能得到一个有序序列了。

思路

要求：给你一个数组 {4,6,8,5,9} , 要求使用堆排序法，将数组升序排序。

我们从最后一个非叶子结点开始（最后一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左子节点至右子节点，从子节点至父节点进行调整，让元素大的成为父节点。

2.找到第二个非叶子节点，也是就是下标为0的4，由于[4,9,8]中9元素最大，4和9交换。

这时，交换导致了子树[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。

此时，步骤一将一个无序序列构造成了一个大顶堆就完成了。

步骤二将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

a.将堆顶元素9和末尾元素4进行交换

b.重新调整结构，使其继续满足堆定义

c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

代码实现

package com.nanzx.tree;

import java.util.Arrays;

public class HeapSort {

	public static void main(String[] args) {
		int[] arr = { 4, 6, 8, 5, 9 };
		heapSort(arr);
		System.out.println(Arrays.toString(arr));
	}

	public static void heapSort(int[] arr) {
		int temp = 0;
		for (int i = arr.length / 2 - 1; i >= 0; i--) {//步骤一：将一个无序序列构造成了一个大顶堆
			adjustHeap(arr, i, arr.length);
		}

		for (int j = arr.length - 1; j > 0; j--) {
			temp = arr[j];
			arr[j] = arr[0];
			arr[0] = temp;
			adjustHeap(arr, 0, j);
		}
	}

	public static void adjustHeap(int[] arr, int i, int length) {
		for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
			int temp = arr[(k - 1) / 2];//父节点
			if ((k + 1) < length && arr[k] < arr[k + 1]) {//比较左右子节点
				k++;
			}
			if (arr[k] > temp) {
				arr[(k - 1) / 2] = arr[k];
				arr[k] = temp;
			}
		}
	}
}

测试堆排序的速度

package com.nanzx.tree;

import java.text.SimpleDateFormat;
import java.util.Date;

public class HeapSort {

	public static void main(String[] args) {
		// 创建8000000个的随机树的数组，八百万
		int[] arr = new int[8000000];
		for (int i = 0; i < 8000000; i++) {
			arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
		}

		Date data1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(data1);
		System.out.println("排序前的时间是=" + date1Str);

		heapSort(arr);

		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序后的时间是=" + date2Str);

	}

	public static void heapSort(int[] arr) {
		int temp = 0;
		for (int i = arr.length / 2 - 1; i >= 0; i--) {
			adjustHeap(arr, i, arr.length);
		}

		for (int j = arr.length - 1; j > 0; j--) {
			temp = arr[j];
			arr[j] = arr[0];
			arr[0] = temp;
			adjustHeap(arr, 0, j);
		}
	}

	public static void adjustHeap(int[] arr, int i, int length) {
		for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
			int temp = arr[(k - 1) / 2];
			if ((k + 1) < length && arr[k] < arr[k + 1]) {
				k++;
			}
			if (arr[k] > temp) {
				arr[(k - 1) / 2] = arr[k];
				arr[k] = temp;
			}
		}
	}
}