数据结构+算法-堆排序

硅谷探秘者 4356 0 0

堆排序(英语:Heapsort)是指利用这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。


以最小堆为例

下沉操作

对于一个非叶子节点的下沉操作指的是:如果父节点大于子节点的任何一个节点,那么父节点就要和子节点中的最小的节点交换。

QQ截图20190512120608.png

代码描述

	/**
	 * 下沉操作,构造小顶堆
	 * @param heap 元素数组
	 * @param k 当前元素下标
	 * @param n 数组长度
	 */
    public void sink(int[] heap,int k,int n) {
        while (k<<1 <= n) {
            int j = k<<1;
            /**
             * 判断左子树大还是右子树大,(当然了,对于小顶堆来说,j指向较小的那个元素)
             */
            if (j < n && compare(heap,j, j+1))
                     j++;
            /**
             * 判断父节点是否大于最小的子节点,如果如果是则交换,不是则返回
             */
            if (!compare(heap,k, j))
                     break;
            exchange(heap,k, j);
            k = j;
        }
    }


排序过程

排序的第一步是对整个无序数组进行整理使其满足二叉堆的性质,这样才能对其进行排序(对于非叶子节点所有的父节点均大于其子节点)。

然后对整个堆进行排序,过程描述如下:

    对于小顶堆来说,根节点就是堆中最小的元素,把根节点(数组第一个元素)与数组最后一个元素交换,此时堆元素的长度-1

    交换以后的数组可能不满足堆的性质,则以根节点开始进行下沉操作,直到数组满足堆得性质。

    然后继续交换第一个节点与最后一个节点,如此反复,直到数组中只有一个节点,排序结束

代码描述

/**
	 * 排序
	 * 首先对一个无序的数组进行下沉操作,以至于满足堆的性质,(所有的父节点均大于其子节点)
	 * 然后对整个堆进行排序
	 * @param heap
	 */
	public void sort(int[] heap) {
	    int n = heap.length-1;
	    /**
	     * 第一个for循环用户构造一个满足堆特点的二叉堆
	     * 对所有的非叶子节点执行下沉操作
	     */
	    for (int k = n>>1; k >= 1; k--)
	        sink(heap, k, n);
	    /**
	     * 对二叉堆进行堆排序
	     * 对于小顶堆来说,根节点就是堆中最小的元素,把根节点(数组第一个元素)与数组最后一个元素交换,此时堆元素的长度-1
	     * 交换以后的数组可能不满足堆的性质,则以根节点开始进行下沉操作,直到数组满足堆得性质。
	     * 然后继续交换第一个节点与最后一个节点,如此反复,直到数组中只有一个节点,排序结束
	     */
	    while (n > 1) {
	    	exchange(heap, 1, n--);
	        sink(heap, 1, n);
	    }
	}


完整代码:

package club.test;

import org.junit.Test;
/**
 * 堆排序(小顶堆为例)
 * @author jiajia
 *
 */
public class TestMain8 {
	@Test
	public void test() {
		int[] a=new int[] {0,2,8,5,3,6};
		sort(a);
		for(int i=0;i<a.length;i++) {
			System.out.print(a[i]+" ");
		}
	}
	/**
	 * 排序
	 * 首先对一个无序的数组进行下沉操作,以至于满足堆的性质,(所有的父节点均大于其子节点)
	 * 然后对整个堆进行排序
	 * @param heap
	 */
	public void sort(int[] heap) {
	    int n = heap.length-1;
	    /**
	     * 第一个for循环用户构造一个满足堆特点的二叉堆
	     * 对所有的非叶子节点执行下沉操作
	     */
	    for (int k = n>>1; k >= 1; k--)
	        sink(heap, k, n);
	    /**
	     * 对二叉堆进行堆排序
	     * 对于小顶堆来说,根节点就是堆中最小的元素,把根节点(数组第一个元素)与数组最后一个元素交换,此时堆元素的长度-1
	     * 交换以后的数组可能不满足堆的性质,则以根节点开始进行下沉操作,直到数组满足堆得性质。
	     * 然后继续交换第一个节点与最后一个节点,如此反复,直到数组中只有一个节点,排序结束
	     */
	    while (n > 1) {
	    	exchange(heap, 1, n--);
	        sink(heap, 1, n);
	    }
	}
	/**
	 * 交换元素
	 * @param heap
	 * @param i
	 * @param j
	 */
	public void exchange(int[] heap,int i,int j) {
        heap[i]=heap[i]+heap[j];
        heap[j]=heap[i]-heap[j];
        heap[i]=heap[i]-heap[j];
	}
	/**
	 * 比较
	 * @param heap
	 * @param i
	 * @param j
	 * @return
	 */
	public boolean compare(int[] heap,int i,int j) {
        return heap[i]>heap[j]?true:false;
    }
	/**
	 * 下沉操作,构造小顶堆
	 * @param heap 元素数组
	 * @param k 当前元素下标
	 * @param n 数组长度
	 */
	public void sink(int[] heap,int k,int n) {
        while (k<<1 <= n) {
            int j = k<<1;
            /**
             * 判断左子树大还是右子树大,(当然了,对于小顶堆来说,j指向较小的那个元素)
             */
            if (j < n && compare(heap,j, j+1))
                     j++;
            /**
             * 判断父节点是否大于最小的子节点,如果如果是则交换,不是则返回
             */
            if (!compare(heap,k, j))
                     break;
            exchange(heap,k, j);
            k = j;
        }
    }
}


猜你喜欢
数据结构与算法 799 思想:把所有需要分成两个集合,一个是待集合,一个是已的集合,每次从未集合顺或随机拿取一个,把它加入到已集合使其有,直到未集合中的被取走完,
数据结构与算法 898 ,若组只有一个元素则无需操作。每次递归束时,左右两个组都是有的,然后对这两个中的进行,使整个组有。直到束。publicclassTest8{ publicstaticint
数据结构与算法 872 思想:希尔是插入的增强版,其主要的思想还是插入的思想。描述:在插入的基础上,对待组进行间隔为inc的分组,然后对每个分组进行直接插入,一次完成后,减小inc
数据结构与算法 972 思想将待集合以该集合中随机的一个为分界点分成左右两个集合,一次使其右边的集合的全部大于左边的集合,然后再分别递归式的对左右两个集合执行上述操作,直到递归集合没有,递归束完
数据结构与算法 894 思想:对冒泡的一种改进,每次从没有的集合a中拿取一个最大或最小的元素,放入有的集合b中,直到a集合中的元素被取完描述:用变量i遍历整个组,用变量j遍历i后面的组,每次遍历i初始
数据结构与算法 1201 思想把所有需要分成两个集合,一个是待集合,一个是已的集合,每次从未集合顺或随机拿取一个,把它加入到已集合使其有,直到未集合中的被取走完,束案例
数据结构与算法 770 思想:每次从没有的集合a中拿取一个最大或最小的元素,放入有的集合b中,直到a集合中的元素被取完描述:用变量i遍历整个组,用变量j遍历i后面的组,每次交换i比j大的元素,使得i遍历过
数据结构与算法 1246 原文链接:https://www.zhihu.com/question/23148377?sort=created基础 时间复杂度 空间复杂度基础 线性表 列表(必学) 链表(必学
归档
2018年11月  12 2018年12月  33 2019年01月  28 2019年02月  28 2019年03月  32 2019年04月  27 2019年05月  33 2019年06月  6 2019年07月  12 2019年08月  12 2019年09月  21 2019年10月  8 2019年11月  15 2019年12月  25 2020年01月  9 2020年02月  5 2020年03月  16 2020年04月  4 2020年06月  1 2020年07月  7 2020年08月  13 2020年09月  9 2020年10月  5 2020年12月  3 2021年01月  1 2021年02月  5 2021年03月  7 2021年04月  4 2021年05月  4 2021年06月  1 2021年07月  7 2021年08月  2 2021年09月  8 2021年10月  9 2021年11月  16 2021年12月  14 2022年01月  7 2022年05月  1 2022年08月  3 2022年09月  2 2022年10月  2 2022年12月  5 2023年01月  3
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job rabbitmq haproxy
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。