Java堆排序

本文详细介绍了Java中堆排序的实现过程,包括大顶堆和小顶堆的概念,以及如何将数组转换为大顶堆并进行排序。通过示例代码展示了如何构建和调整大顶堆,最终实现整个数组的排序。堆排序是一种高效的排序算法,适用于大数据量的排序场景。

摘要生成于 C知道 ,由 DeepSeek-R1 满血版支持, 前往体验 >

Java堆排序

1、大顶堆,父节点大于任意一个子节点,升序排序用大顶堆
在这里插入图片描述

2、小顶堆,任何一个字节点都比父节点大,降序排序用小顶堆

3、思路:把数组转为大顶堆的树,后,交换第一个和最后一个的位置,取出最后一个,在组成大顶堆,不断循环,直到取到最后一个。

4、需要注意的问题:
转成大顶堆后交换0和arr.length的位置,在转大顶堆的过程中,从最后一个节点的父节点开始找,如果这个节点比他的左或右节点小,那么交换位置,交换位置后,可能会破坏之前排好的堆,所以之前排好的堆需要重新调(递归)

5、代码实现

// Copyright 2016-2101 Pica.
package sort;

import java.util.Arrays;

public class HeapSort {
	public static void main(String[] args) {
		int[] arr = new int[]{9,6,8,7,0,1,10,4,2};
		heapSort(arr);
		System.out.println(Arrays.toString(arr));

	}

	public static void heapSort(int[] arr){
		//开始位置是最后一个非叶子节点,即最后一个节点的父节点
		int start = (arr.length-1)/2;
		//循环调整大顶堆
		for (int i = start;i>=0;i--){
			maxHeap(arr,arr.length,i);
		}
		//先把数组中的第0个和堆中的最后一个数交换位置,再把前面的处理为大顶堆
		for (int i = arr.length-1; i >0 ; i--) {
			int temp =arr[0];
			arr[0]=arr[i];
			arr[i]=temp;
			maxHeap(arr,i,0);
		}
	}


	/**
	 *数组转变成大顶堆
	 * @param arr
	 * @param size 调整多少
	 * @param index 从那个开始调整
	 */
	public static void maxHeap(int[] arr,int size,int index){
		//左子节点
		int leftNode = 2*index+1;
		//右子节点
		int rightNode=2*index+2;
		int max =index;
		//和两个子节点分别对比,找出最大的节点
		 if (leftNode<size && arr[leftNode]>arr[max]){
			 max=leftNode;
		 }
		if (rightNode<size && arr[rightNode]>arr[max]){
			max=rightNode;
		}
		//交换位置,如果当前值就是最大的就不用交换
		if (max!=index){
			int temp =arr[index];
			arr[index]=arr[max];
			arr[max]=temp;
			//交换位置后,可能会破坏之前排好的堆,所以之前排好的堆需要重新调整
			maxHeap(arr,size,max);
		}



	}

}
### Java堆排序的实现与原理 #### 1. 堆排序的基本原理 堆排序是一种基于比较的排序算法,主要依赖于一种称为“堆”的特殊数据结构。堆可以分为两种形式:**顶堆**和**小顶堆**。 - **顶堆**是指父节点的值总是于等于子节点的值。 - **小顶堆**则是指父节点的值总是小于等于子节点的值。 堆排序的核心思想是先将待排序的数据构建为一个顶堆(或小顶堆)。对于升序排序来说,通常采用顶堆;而对于降序排序,则使用小顶堆。随后不断取出堆顶元素(即当前最值或最小值),并将剩余部分重新调整成一个新的堆,直到所有元素都被处理完毕[^3]。 #### 2. 构建堆的过程 为了完成堆排序,需要解决两个核心问题: 1. 将无序数组转换为一个合法的顶堆。 2. 在每次移除堆顶元素后,能够动态维护剩下的部分仍满足堆的定义。 ##### (a) 调整堆的操作 假设已经有一个接近堆结构的部分数组,可以通过自底向上的方式逐步修复堆属性。具体做法是从某个非叶子节点开始向下遍历,如果发现该节点不符合堆的要求(比如在顶堆中,父节点小于子节点),则交换父子节点的位置,并继续递归地检查被交换后的子节点是否仍然违反堆规则[^4]。 以下是调整堆的一个伪代码表示: ```java private void heapify(int[] array, int length, int i) { int largest = i; // 初始化最值索引为根节点 int leftChild = 2 * i + 1; int rightChild = 2 * i + 2; // 如果左孩子存在且于当前最值 if (leftChild < length && array[leftChild] > array[largest]) { largest = leftChild; } // 如果右孩子存在且于当前最值 if (rightChild < length && array[rightChild] > array[largest]) { largest = rightChild; } // 如果最值不是根节点,交换它们并递归调用heapify if (largest != i) { swap(array, i, largest); heapify(array, length, largest); // 继续下沉 } } ``` ##### (b) 初始堆化过程 初始阶段,我们需要把整个输入数组转化为一个完整的堆。由于完全二叉树的特点决定了最后一个非叶节点位于 `(n/2)-1` 的位置,所以可以从这个位置向前依次对每一个内部节点执行 `heapify` 操作[^1]。 #### 3. 完整的堆排序流程 一旦完成了初始化堆的工作之后,就可以按照如下步骤来进行最终的排序: 1. 取出堆顶元素放到已排序区域的最后一项; 2. 缩短未排序区间的长度; 3. 对新的未排序区间再次进行 `heapify` 处理以恢复堆特性; 4. 循环上述三步直至全部元素都进入到了已排序状态之中。 下面是完整的 Java 实现代码: ```java public class HeapSort { public static void sort(int[] array) { int n = array.length; // Build max heap. for (int i = n / 2 - 1; i >= 0; i--) { heapify(array, n, i); } // Extract elements one by one from the heap and place them at their correct positions. for (int i = n - 1; i > 0; i--) { // Move current root to end of unsorted part. swap(array, 0, i); // Call max heapify on reduced heap. heapify(array, i, 0); } } private static void heapify(int[] array, int length, int i) { int largest = i; // Initialize largest as root int leftChild = 2 * i + 1; int rightChild = 2 * i + 2; // If left child is larger than root if (leftChild < length && array[leftChild] > array[largest]) { largest = leftChild; } // If right child is larger than largest so far if (rightChild < length && array[rightChild] > array[largest]) { largest = rightChild; } // If largest is not root if (largest != i) { swap(array, i, largest); heapify(array, length, largest); // Recursively heapify affected sub-tree } } private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } public static void main(String[] args) { int[] data = {4, 10, 3, 5, 1}; System.out.println("Original Array:"); printArray(data); sort(data); System.out.println("\nSorted Array:"); printArray(data); } private static void printArray(int[] array) { for (int value : array) { System.out.print(value + " "); } } } ``` 这段程序展示了如何通过堆排序技术有效地对一组随机数列实施升序排列[^2]。 --- ### 总结 堆排序以其时间复杂度 $O(n \log n)$ 和原地工作的特点,在很多场合下表现出色。虽然它不像快速排序那样平均表现更佳,但它具有最坏情况下的线性对数级效率优势[^5]。
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值