排序之堆排序

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

什么是堆排序?

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

堆排序的步骤

  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)。虽然它的实现相对复杂一些,但是一旦理解了其基本思想,就可以很容易地掌握这种算法。希望这篇文章能帮助你更好地理解和应用堆排序。

相关推荐

  1. 排序排序

    2024-01-13 08:14:01       41 阅读
  2. 排序算法】排序

    2024-01-13 08:14:01       46 阅读
  3. 排序!!

    2024-01-13 08:14:01       7 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-01-13 08:14:01       18 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-01-13 08:14:01       19 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-01-13 08:14:01       19 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-01-13 08:14:01       20 阅读

热门阅读

  1. Nacos_Linux上部署nacos

    2024-01-13 08:14:01       38 阅读
  2. Flink

    Flink

    2024-01-13 08:14:01      35 阅读
  3. 修改默认负载均衡策略(Ribbon)

    2024-01-13 08:14:01       40 阅读
  4. 使用spark将MongoDB数据导入hive

    2024-01-13 08:14:01       36 阅读
  5. CompletableFuture、ListenableFuture高级用列

    2024-01-13 08:14:01       29 阅读
  6. STM32 i2c从机模式中断处理参考

    2024-01-13 08:14:01       31 阅读
  7. 9个Linux网络命令

    2024-01-13 08:14:01       33 阅读
  8. 基本数据结构 | 并查集

    2024-01-13 08:14:01       44 阅读