排序之堆排序

在计算机科学中，排序是一种常见的操作。它的目标是将一组元素按照一定的顺序排列。不同的排序算法有不同的性能特性，选择哪种算法取决于具体的应用场景和需求。本文将介绍一种非常有效的排序算法——堆排序。

什么是堆排序？

堆排序是一种基于二叉堆的比较排序算法。它的主要思想是将待排序的序列构造成一个大顶堆（或小顶堆），然后将堆顶的最大元素与末尾元素进行交换，再调整剩余元素为大顶堆，如此反复，直到整个序列有序。

堆排序的步骤

1. 构建大顶堆：首先，我们需要将待排序的序列构造成一个大顶堆。这个过程可以通过从最后一个非叶子节点开始，依次向上调整每个节点来实现。

2. 堆顶堆底进行交换：然后，我们将堆顶的元素（即当前最大的元素）与堆底的元素进行交换。这样，最大元素就位于了正确的位置。

3. 调整剩余元素为大顶堆：最后，我们需要将剩余的元素重新调整为大顶堆。这个过程同样可以通过从最后一个非叶子节点开始，依次向上调整每个节点来实现。

4. 重复以上步骤，直到整个序列有序：这就是堆排序的基本过程。

时间复杂度

时间复杂度：O(nlogn)

空间复杂度：O(1)。

代码实现

package sort;

import java.util.Arrays;
//堆排序
public class HeapSort {

	public static void main(String[] args) {
		int[] arr = {5,7,4,2,0,3,1,6};
		//构建大顶堆
		for(int i =arr.length;i>=0;i--) {
			adjust(arr, i, arr.length);
		}
		//堆顶堆底进行交换
		for(int j = arr.length-1;j>=0;j--) {
			int temp = arr[j];
			arr[j] =arr[0];
			arr[0] = temp;
			adjust(arr, 0, j);
		}
		System.out.println(Arrays.toString(arr));
	}
	/**
	 * 堆的维护
	 * @param arr
	 * @param parent
	 * @param length
	 */
	public static void adjust(int[] arr,int parent,int length) {
		int child = 2*parent+1;
		while(child<length) {
			//定义右孩子，找到左右孩子的最大值
			int rchild = child+1;
			if(rchild<length && arr[child]<arr[rchild]) {
				child++;
			}
			//父节点进行对比
			if(arr[parent]<arr[child]) {
				//父节点进行交换
				int temp = arr[parent];
				arr[parent] = arr[child];
				arr[child] = temp;
				parent = child;
				child = 2*child+1;
			}else {
				break;
			}
		}	
	}
}

总结

堆排序是一种非常高效的排序算法，其时间复杂度为O(nlogn)，空间复杂度为O(1)。虽然它的实现相对复杂一些，但是一旦理解了其基本思想，就可以很容易地掌握这种算法。希望这篇文章能帮助你更好地理解和应用堆排序。