1、排序算法概述

常用的内部排序方法有：交换排序（冒泡排序、快速排序）、选择排序（简单选择排序、堆排序）、插入排序（直接插入排序、希尔排序）、归并排序、基数排序（一关键字、多关键字）。

所需辅助空间最多：归并排序

所需辅助空间最少：堆排序

平均速度最快：快速排序

不稳定：快速排序，希尔排序，堆排序。

选择排序算法的依据：任何排序算法在数据量小的时候基本体现不出来差距。选择依据有：

1.数据的规模 ：当数据规模较小时，选择直接插入排序或冒泡排序。
2.数据的类型 ：如全部是正整数，那么考虑使用桶排序为最优。
3.数据已有的顺序 ：快排是一种不稳定的排序（当然可以改进），对于大部分排好的数据，快排会浪费大量不必要的步骤。

数据量极小，而且已经基本排好序，冒泡是最佳选择。我们说快排好，是指大量随机数据下，快排效果最理想。而不是所有情况。

2、堆排序时空复杂度

最好时间复杂度O(logn)，最差时间复杂度O(nlogn)，平均时间复杂度O(nlogn)，空间复杂度O(1)，是一种不稳定的排序算法。

3、堆排序原理

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

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

（拓展）完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

堆排序的原理就是这样，先构造出来大顶堆（假设从小到大排序），然后取出堆顶元素（也就是最大的元素），将其与末尾元素进行交换，此时末尾元素为最大值。然后再将剩余的n-1元素构造成大顶堆，再取出堆顶元素与本次数组的末尾元素进行交换，如此反复执行，排序就完成了。

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子：

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]  

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

4、堆排序思路

将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

5、堆排序举例说明

要排序数组：int[] arr={4,6,8,5,9};

步骤一构造初始堆。

将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。

1.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。

2.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。

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

此时，我们就将一个无需序列构造成了一个大顶堆。

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

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

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

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

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

6、堆排序代码

public class HeapSort {
	public static void main(String[] args) {
		int[] arr = { 50, 10, 90, 30, 70, 40, 80, 60, 20, 70, 40, 80, 60, 90 };
		System.out.println("排序之前：");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		// 堆排序
		heapSort(arr);
		System.out.println();
		System.out.println("排序之后：");
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}

	/**
	 * 堆排序
	 */
	private static void heapSort(int[] arr) {
		// 1.将待排序的序列构建成一个大顶堆
		for (int i = arr.length / 2 - 1; i >= 0; i--) {
			// 从第一个非叶子结点从下至上，从右至左调整结构
			adjustHeap(arr, i, arr.length);
		}
		// 2.调整堆结构+交换堆顶元素与末尾元素
		// 逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
		for (int j = arr.length - 1; j > 0; j--) {
			swap(arr, 0, j);// 将堆顶元素与末尾元素(当前未经排序子序列的最后一个记录)进行交换
			adjustHeap(arr, 0, j);// 重新对堆进行调整(重新检查堆是否符合大顶堆，不符合则要调整)
		}
	}

	/**
	 * 调整大顶堆-构建堆的过程（仅是调整过程，建立在大顶堆已构建的基础上）
	 * 
	 * @param arr
	 *            需要排序的数组
	 * @param i
	 *            需要构建堆的根节点的序号
	 * @param length
	 *            数组的长度
	 */
	public static void adjustHeap(int[] arr, int i, int length) {
		int temp = arr[i];// 先取出当前元素i
		// 从i结点的左子结点开始，也就是2i+1处开始, k*2+1表示当前节点的下一个子节点
		for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
			if (k + 1 < length && arr[k] < arr[k + 1]) {
				// 如果左子结点小于右子结点，k指向右子结点
				k++;
			}
			if (arr[k] > temp) {
				// 如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）,
				arr[i] = arr[k];
				i = k;
				// 然后进入下轮循环，调整当前节点与其子节点
			} else {
				break;
			}
		}
		arr[i] = temp;// 将temp值放到最终的位置
	}

	// 交换元素位置
	private static void swap(int[] arr, int index1, int index2) {
		int tmp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = tmp;
	}
}

// 排序之前：
// 50 10 90 30 70 40 80 60 20 70 40 80 60 90 
// 排序之后：
// 10 20 30 40 40 50 60 60 70 70 80 80 90 90

目录CONTENT

java排序算法之堆排序