选择排序—堆排序（Heap Sort）

发布时间：2018-04-19作者：laosun阅读（1902）

java选择排序—堆排序（Heap Sort），堆排序是一种树形选择排序，是对直接选择排序的有效改进。堆的定义如下：具有n个元素的序列（k1,k2,...,kn),当且仅当满足

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

基本思想：

堆的定义如下：具有n个元素的序列（k1,k2,...,kn),当且仅当满足

时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。
若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如：

（a）大顶堆序列：（96, 83,27,38,11,09)

(b) 小顶堆序列：（12，36，24，85，47，30，53，91）

初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。

因此，实现堆排序需解决两个问题：
1. 如何将n 个待排序的数建成堆；
2. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。

首先讨论第二个问题：输出堆顶元素后，对剩余n-1元素重新建成堆的调整过程。
调整小顶堆的方法：

1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。

2）将根结点与左、右子树中较小元素的进行交换。

3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法（2）.

4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法（2）.

5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。

称这个自根结点到叶子结点的调整过程为筛选。如图：

再讨论对n 个元素初始建堆的过程。
建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。

1）n 个结点的完全二叉树，则最后一个结点是第个结点的子树。

2）筛选从第个结点为根的子树开始，该子树成为堆。

3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）

算法的实现：

从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

/**
 * Java实现快速排序算法 
 * 由大到小排序 
 * 两个步骤：1，建堆  2，对顶与堆的最后一个元素交换位置 
 */
public class HeapSort {

	public static void main(String[] args) {
		int a[] = { 3, 1, 5, 7, 2, 4, 9, 6, 10, 8 };
		HeapSort obj = new HeapSort();
		System.out.println("初始值：");
		obj.print(a);

		for (int i = 0; i < a.length; i++) {
			obj.createLittleHeap(a, a.length - 1 - i);// 创建堆,创建的是小顶堆。每次循环完，二叉树的根节点都是最小值，所以与此时的未排好部分最后一个值交换位置
			obj.swap(a, 0, a.length - 1 - i);// 与最后一个值交换位置，最小值找到了位置
			obj.print(a);
			System.out.println();

		}

		System.out.println("\n排序后：");
		obj.print(a);

	}

	/*
	 * 创建小顶堆：双亲节点小于子节点的值。从叶子节点开始，直到根节点。这样建立的堆定位最小值
	 */
	private void createLittleHeap(int[] data, int last) {
		for (int i = (last - 1) / 2; i >= 0; i--) { // 找到最后一个叶子节点的双亲节点
			// 保存当前正在判断的节点
			int parent = i;
			// 若当前节点的左子节点存在，即子节点存在
			while (2 * parent + 1 <= last) {
				// biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点
				int bigger = 2 * parent + 1;// bigger指向左子节点
				if (bigger < last) { // 说明存在右子节点

					if (data[bigger] > data[bigger + 1]) { // 右子节点>左子节点时

						bigger = bigger + 1;
					}
				}
				if (data[parent] > data[bigger]) { // 若双亲节点值大于子节点中最大的
					// 若当前节点值比子节点最大值小，则交换2者得值，交换后将biggerIndex值赋值给k
					swap(data, parent, bigger);
					parent = bigger;
				} else {
					break;
				}
			}
		}
	}

	public void print(int a[]) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}

	public void swap(int[] data, int i, int j) {
		if (i == j) {
			return;
		}
		data[i] = data[i] + data[j];
		data[j] = data[i] - data[j];
		data[i] = data[i] - data[j];
	}
}

堆排序需要双层循环，第一层控制循环多少次，第二层得到每次的最小值（小顶堆）

import java.util.ArrayList;

public class Solution32 {
	/*
	 * 输入n个整数，找出其中最小的K个数。 例如输入4,5,1,6,2,7,3,8这8个数字， 则最小的4个数字是1,2,3,4,。
	 */
	public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
		ArrayList<Integer> result = new ArrayList<Integer>();
		if (k > input.length)
			return result;
		for (int i = 0; i < k; i++) {// 只排前k次
			heapSort(input, i, input.length);// 进行第i次排序
			result.add(input[i]);
		}
		return result;
	}

	private void heapSort(int[] input, int root, int end) {// 小顶堆实现
		for (int j = end - 1; j >= root; j--) {
			int parent = (j + root - 1) / 2;// 算出j节点的双亲节点的序号
			if (input[parent] > input[j]) {// 双亲节点大于当前节点，交换位置。
				int temp = input[j];
				input[j] = input[parent];
				input[parent] = temp;
			}
		}
	}

	public static void main(String[] args) {
		int[] str = { 4, 5, 1, 6, 2, 7, 3, 8 };
		Solution32 s = new Solution32();
		System.out.print(s.GetLeastNumbers_Solution(str, 4));

	}
}

/**
 * Java实现堆排序算法（改进）  
 * 由大到小排序 
 * 两个步骤：1，建堆  2，对顶与堆的最后一个元素交换位置
 */
public class HeapSort {

	public static void main(String[] args) {
		int a[] = { 3, 1, 5, 7, 2, 4, 9, 6, 10, 8 };
		HeapSort obj = new HeapSort();
		System.out.println("初始值：");
		obj.print(a);

		for (int i = 0; i < a.length; i++) {
			obj.createLittleHeap(a, a.length - 1 - i);// 创建堆,创建的是小顶堆。每次循环完，二叉树的根节点都是最小值，所以与此时的未排好部分最后一个值交换位置
			obj.swap(a, 0, a.length - 1 - i);// 与最后一个值交换位置，最小值找到了位置
			obj.print(a);
			System.out.println();

		}

		System.out.println("\n排序后：");
		obj.print(a);

	}

	/*
	 * 创建小顶堆：双亲节点小于子节点的值。从叶子节点开始，直到根节点。这样建立的堆定位最小值
	 */
	private void createLittleHeap(int[] data, int last) {
		for (int i = last; i > 0; i--) {
			int parent = (i - 1) / 2;// 当前节点的双亲节点
			if (data[parent] > data[i])
				swap(data, parent, i);
		}
	}

	public void print(int a[]) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}

	public void swap(int[] data, int i, int j) {
		if (i == j) {
			return;
		}
		data[i] = data[i] + data[j];
		data[j] = data[i] - data[j];
		data[i] = data[i] - data[j];
	}
}

分析:

设树深度为k，。从根到叶的筛选，元素比较次数至多2(k-1)次，交换记录至多k 次。所以，在建好堆后，排序过程中的筛选次数不超过下式：