内容简介:首先我们来看看什么叫做堆排序?若在输出堆顶的最小值之后,使得剩余的n-1个元素的序列重新又构成一个堆,则得到n个元素中的次小值,如此反复,便能得到一个有序序列,称这个过程为堆排序。再来看看总结一下基本思想:
堆排序
一、概述
首先我们来看看什么叫做堆排序?
若在输出堆顶的最小值之后,使得剩余的n-1个元素的序列重新又构成一个堆,则得到n个元素中的次小值,如此反复,便能得到一个有序序列,称这个过程为堆排序。
再来看看总结一下基本思想:
- 将无序序列建成一个堆
- 输出堆顶的最小(大)值
- 使剩余的n-1个元素又调整成一个堆,则可得到n个元素的次小值
- 重复执行,得到一个有序序列
通过上面的规律发现两个问题,而堆 排序 需要解决这两个问题:1.如何建堆? 2.如何调整?
二、如何建堆
1.什么是堆?
n个元素的序列{k1,k2,…,kn},当且仅当满足下列关系时,成为堆:
如果将序列看成一个完全二叉树,非终端结点的值均小于或大于左右子结点的值。
利用树的结构特征来描述堆,所以树只是作为堆的描述工具,堆实际是存放在线形空间中的。
解释: 从上面可以知道,当父节点大于左右孩子节点 或者父节点小于节点的时候,可以称为堆,前者称为大顶堆,后者称为小顶堆。
2.建堆
从第n/2 向下取整 个元素起,至第一个元素止,进行反复筛选,如果我们要建立大顶堆,先比较左右孩子的大小,将比较大的孩子和父节点进行比较。
因为数组的元素一共是7个元素,我们应该从第3个元素,首先我们应该比较第3个元素的左右孩子的大小,然后再进行调整。
代码如下:
Copy
// 建立大顶堆 publicvoidbuildHeap(int[] arr){ for (int i = arr.length /2 -1; i >=0; i--) { //从第一个非叶子结点从下至上,从右至左调整结构 adjustHeap(arr, i, arr.length); } } /** * 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上) * *@param arr *@param i *@param length */ publicstaticvoidadjustHeap(int[] arr,int i,int length) { int temp = arr[i];//先取出当前元素i for (int k = i *2 +1; k < length; k = k *2 +1) {//从i结点的左子结点开始,也就是2i+1处开始 if (k +1 < length && arr[k] < arr[k +1]) {//如果左子结点小于右子结点,k指向右子结点 k++; } if (arr[k] > temp) {//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换) arr[i] = arr[k]; i = k; }else { break; } } arr[i] = temp;//将temp值放到最终的位置 } /** * 交换元素 * *@param arr *@param a *@param b */ publicstaticvoidswap(int[] arr,int a,int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; }
三、如何调整
当我们将数组进行建立大顶堆或者小顶堆的时候,我们就会发现堆顶元素必然是该排序数组的最大或者是最小的那个数据。如何在输出堆顶元素后调整,使之成为新堆?
- 输出堆顶元素后,以堆中最后一个元素替代之
- 将根结点与左、右子树根结点比较,并与小者交换
- 重复直至叶子结点,得到新的堆
解释:
这时候我们将堆顶元素和最后一个元素进行交换,那么我们调整前n-1个元素成堆,反复操作即可
四、算法分析
时间效率:O(nlog2n) O(nlog2n)
空间效率:O(1) O(1)
稳 定 性:不稳定
适用于n 较大的情况
五、完整代码
Copy
publicclassHeapSort { publicstaticvoidmain(String[] args) { int[] arr = {9,8,7,6,5,4,3,2,1}; sort(arr); System.out.println(Arrays.toString(arr)); } publicstaticvoidsort(int[] arr) { //1.构建大顶堆 for (int i = arr.length /2 -1; i >=0; i--) { //从第一个非叶子结点从下至上,从右至左调整结构 adjustHeap(arr, i, arr.length); } //2.调整堆结构+交换堆顶元素与末尾元素 for (int j = arr.length -1; j >0; j--) { swap(arr,0, j);//将堆顶元素与末尾元素进行交换 adjustHeap(arr,0, j);//重新对堆进行调整 } } /** * 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上) * *@param arr *@param i *@param length */ publicstaticvoidadjustHeap(int[] arr,int i,int length) { int temp = arr[i];//先取出当前元素i for (int k = i *2 +1; k < length; k = k *2 +1) {//从i结点的左子结点开始,也就是2i+1处开始 if (k +1 < length && arr[k] < arr[k +1]) {//如果左子结点小于右子结点,k指向右子结点 k++; } if (arr[k] > temp) {//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换) arr[i] = arr[k]; i = k; }else { break; } } arr[i] = temp;//将temp值放到最终的位置 } /** * 交换元素 * *@param arr *@param a *@param b */ publicstaticvoidswap(int[] arr,int a,int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } }
Linux公社的RSS地址 : https://www.linuxidc.com/rssFeed.aspx
本文永久更新链接地址: https://www.linuxidc.com/Linux/2018-12/155785.htm
以上所述就是小编给大家介绍的《经典排序之堆排序详解》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- PG归并排序算法详解
- Java快速排序图文详解
- Elasticsearch搜索相关性排序算法详解
- Go语言 channel如何实现归并排序中的merge函数详解
- 图形化排序算法比较:快速排序、插入排序、选择排序、冒泡排序
- 排序算法下——桶排序、计数排序和基数排序
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。