堆排序

堆排序

堆的定义

  • 堆(heap),这里所说的堆是数据结构中的堆,而不是内存模型中的堆。堆通常是一个可以被看做一棵树,它满足下列性质:
  • [性质一] 堆中任意节点的值总是不大于(不小于)其子节点的值;
  • [性质二] 堆总是一棵完全树
  • 将任意节点不大于其子节点的堆叫做最小堆或小根堆,而将任意节点不小于其子节点的堆叫做最大堆或大根堆。常见的堆有二叉堆、左倾堆、斜堆、二项堆、斐波那契堆等等。

排序的过程

  1. 将数组建成最大堆或者最小堆
  2. 取出堆顶的数据和数组末尾的数据交换,此时对前面的数据再次建堆,再取堆顶的数据和数组中的倒数第二个交换,…………………….

代码实现

构造大顶堆

  • 实现从大到小的排序

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970

public class HeapSort { /** * 构造大顶堆 * 1. 根节点的值一定要比子节点的值大 * 堆的向下调整 * @param array 需要调整的数组 * @param start 调整的起始位置 * @param end 调整的终止位置 * 索引从0开始 * 当前节点的左节点: 2*i+1 * 右节点: 2**i+2 */ public static void max_heap_down(int[] array,int start,int end){ int currentIndex=start; //保存当前节点的下标 int leftIndex=2*currentIndex+1; //当前节点左节点的下标 //当当前节点的左节点的下标小于终止下标的时候,因为堆是一个完全的二叉树,因此只要没有左子树就一定没有右子树,因此只需要判断左节点的下标即可 //只要满足这个条件就表示一定存在左右节点 while(leftIndex<end){ //当左节点的值小于右节点,那么此时只需要将当前值和右节点的值比较,这里的leftIndex+1是右子节点的下标 //如果没有执行if体内的语句,那么此时的左右节点最大的下标就是左节点的下标 if(array[leftIndex]<array[leftIndex+1]){ leftIndex++; //此时的下标编程右节点的下标 } //如果当前节点大于等于左右子节点中的最大值,那么就不用调整了,直接跳出 if (array[currentIndex]>=array[leftIndex]) { break; }else { //如果小于,此时需要调整,将当前节点和左右子节点最大值交换 int temp=array[currentIndex]; //交换数字 array[currentIndex]=array[leftIndex]; array[leftIndex]=temp; currentIndex=leftIndex; //此时的当前节点的下标 leftIndex=2*currentIndex+1; //当前节点的左子节点也需要改变了 } } } /** * 堆排序,从小到大 * @param array 待排序的数组 */ public static void heap_sort_asc(int[] array){ //从索引为array.length/2-1的位置到0,开始向下调整,那么调整好的数组就是一个大顶堆 for(int i=array.length/2-1;i>=0;i--){ //进行向下调整 max_heap_down(array, i, array.length-1); } //从最后一个元素开始对序列进行调整,不断的调整,直到第一个元素 for (int i = array.length-1; i >0; i--) { //此时array[0]就是最大的元素,因此和最后一个元素交换 int temp=array[i]; array[i]=array[0]; array[0]=temp; //此时最后一个元素就是最大的,因此我们对前面的元素继续构造大顶堆 max_heap_down(array, 0, i-1); } } public static void main(String[] args) { int[] array={12,3,4,45,1,45,6,72,4}; heap_sort_asc(array); for (int i = 0; i < array.length; i++) { System.out.println(array[i]); } }}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

Codeforces 842A Kirill And The Game【暴力,水】

A. Kirill And The Game time limit per test:2 seconds memory limit per test:256 m...

2767
来自专栏ml

hdu---(1325)Is It A Tree?(并查集)

Is It A Tree? Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3276...

3088
来自专栏机器学习从入门到成神

数据结构之树、森林和二叉树的转换

树转换为二叉树 (1)加线。在所有兄弟结点之间加一条连线。 (2)去线。树中的每个结点,只保留它与第一个孩子结点的连线,删除它与其它孩子结点之间的连线。...

872
来自专栏Java开发者杂谈

堆排序与快速排序

前言   前面差不多学习了插入排序、选择排序、冒泡排序、归并排序。这些排序除了归并排序在时间上消耗为:θ(nlgn)外,其余排序时间消耗都为:θ(n2).  接...

35011
来自专栏LeetCode

LeetCode 162. Find Peak Element

题目大意:在一个数组中寻找一个峰值,题目的最后一句话是一个关键,如果没有这句话,我想大多数首先想到的就是一个一个的判断,这样的话算法复杂度是O(n),实际上本题...

100
来自专栏数据结构与算法

BZOJ 4152: [AMPPZ2014]The Captain(最短路)

Description 给定平面上的n个点,定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|),求从1号点走到n号点的最小费用...

3297
来自专栏机器学习算法全栈工程师

动态规划系列之最长递增子序列问题解答

今天和大家分享的是动态规划经典问题:最长递增子序列问题解答。(似乎BAT等各大公司都喜欢在面试的时候对动态规划系列经典问题进行笔试。 题目描述: 给定一个整数序...

2887
来自专栏King_3的技术专栏

leetcode-908-最小差值 I

给定一个整数数组 A,对于每个整数 A[i],我们可以选择任意 x 满足 -K <= x <= K,并将 x 加到 A[i] 中。

1012
来自专栏算法修养

FZU 2150 Fire Game(BFS)

Problem 2150 Fire Game Accept: 1302    Submit: 4569 Time Limit: 1000 mSec    M...

2904
来自专栏数据结构与算法

POJ3233Matrix Power Series(矩阵快速幂)

给出$n \times n$的矩阵$A$,求$\sum_{i = 1}^k A^i $,每个元素对$m$取模

654

扫码关注云+社区