`
nijiaben
  • 浏览: 130364 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

就地堆排序

J# 
阅读更多
   本文最先发布在我的个人博客http://www.lovestblog.cn
   今天来了解一下堆排序的问题,“堆”是个很有趣的结构。通常“堆”是通过数组来实现的,这样可以利用数组的特点快速定位指定索引的元素。而对“堆”的操作中定位某个元素简直就是家常便饭。为什么这么说呢,我们来看看“堆”的定义:

在起始索引为 0 的“堆”中:
1) 堆的根节点将存放在位置 0
2) 节点 i 的左子节点在位置 2 * i + 1
3) 节点 i 的右子节点在位置 2 * i + 2
4) 节点 i 的父节点在位置 floor( (i - 1) / 2 )   : 注 floor 表示“取整”操作

在起始索引为 1 的“堆”中:
1) 堆的根节点将存放在位置 1
2) 节点 i 的左子节点在位置 2 * i
3) 节点 i 的右子节点在位置 2 * i + 1
4) 节点 i 的父节点在位置 floor( i / 2 )           : 注 floor 表示“取整”操作

以下是一个“堆”的图例:

因此,当我们得知某个节点的索引为 i 时,可以通过以下“堆”的定义很容易地定位到它的子节点和父节点。

不仅如此,“堆”还有个特性:每个节点的键值一定总是大于(或小于)它的父节点。如果我们修改了某个节点的键值,这样就会破坏“堆”的这个特性,因此这时我们就要根据该节点的新键值与它的父节点和子节点的键值进行比较,对该节点进行“上移”或者“下移”操作,使之能够重新放置到合适位置。

这里我们了解一下“堆”的这两个很重要的操作:“上移”和“下移”。

这里我们假设这是一个“最大堆”,即“堆”的根节点保存的是键值最大的节点。即“堆”中每个节点的键值都总是大于它的子节点。

当某节点的键值大于它的父节点时,这时我们就要进行“上移”操作,即我们把该节点移动到它的父节点的位置,而让它的父节点到它的位置上,然后我们继续判断该节点,直到该节点不再大于它的父节点为止才停止“上移”。

现在我们再来了解一下“下移”操作。当我们把某节点的键值改小了之后,我们就要对其进行“下移”操作。首先,我们要取该节点的两个左右子节点中键值较大的一个,与该节点进行比较,如果该节点小于它的这个子节点,就把该节点移动到它的子节点的位置,而让它原来的子节点升到它的位置上。然后我们继续判断该节点,直到该节点不再小于它的左右子节点为止才停止“下移”。

现在我们再来看看如何把一个无序的序列建立成为一个“堆”?

根据“堆”的特性,我们可以从无序序列的最后一个节点的父节点开始,对其进行“下移”操作,直到序列的第一个节点为止。这样就可以保证每个节点都在合适的位置上,也就建立起了一个“堆”。

但是“堆”并不是一个完全排序的序列,因为“堆”只保证了父节点与子节点的位置关系,但并不保证左右子节点的位置关系。那么我们如何进行“堆排序”呢?

由于一个“堆”的根节点必然是整个序列中最大的元素,因此对于一个排序的序列而言,每个“堆”中我们只能得到一个有效的元素。如果我们拿掉根节点,再对剩下的序列重新排列组成一个“堆”,反复如此,我们就可以依次得到一个完整的排序序列了。

当然,为了简化操作,每次我们只需要把根节点与最后一个位置的节点交换,然后把最后一个位置排除之外,对根节点进行“下移”操作即可。

      下面展示一段代码简单实现了堆排序,上面的文字转载自http://jaskell.blogbus.com/logs/3272503.html,因为我觉得他说得比清楚了,我只是附上自己写的一段代码,这样看我代码会更容易理解了,希望能更加清晰理解堆排序:
package org.rjb.Heap;
/**
 * 通过不断建大顶堆进行排序
 * @author ljp
 *
 */
public class HeapTest {
	public static void main(String args[]){
		//待排序的数组
		int num[]={3,1,5,7,8,2,0,9};
		//创建堆,并排好序
		createHeap(num);
		for(int j=0;j<num.length;j++){
			System.out.print(num[j]+" ");
		}System.out.println();	
	}
	/**
	 * 创建大顶堆
	 * @param num
	 */
	public static void createHeap(int[] num){
		//从最后一个节点开始,对第i个节点,其父节点的位置为(int)Math.floor((i-1)/2)
		for(int i=num.length-1;i>0;i--){
			//如果当前节点比其父节点大的话就把当前节点上虑,既和父节点交换位置
			if(num[i]>num[(int)Math.floor((i-1)/2)]){
				siftUp(num,(int)Math.floor(i/2-1),i);			
			}
		}
	}
	/**
	 * 上虑操作
	 * @param num 待排序的数组
	 * @param h 下虑元素所处的层数
	 * @param key 当前节点在数组中的位置
	 */
	public static void siftUp(int[] num,int h,int key){
		//先交换父子节点的位置
		int temp=num[key];
		num[key]=num[(int)Math.floor((key-1)/2)];
		num[(int)Math.floor((key-1)/2)]=temp;
		//对交换之后的节点可能存在下虑,既如果比子节点的键值要小的话还要和子节点位置进行互换
		siftDown(num,h,key);
	}
	/**
	 * 下滤操作
	 * @param num
	 * @param h
	 * @param key
	 */
	public static void siftDown(int[] num,int h,int key){
		//lastLayer表示的是最后那层所在的层数
		int lastLayer=(int)Math.floor(num.length/2-1);
		//下虑操作最多下虑到最后一层
		while(h<lastLayer){
			//maxChild记录的是键值最大的子孩子
			int maxChild=0;
			//flag用来标识当前节点是否有子孩子
			boolean flag=false;
			//index用来表示子孩子中具有最大键值的那个所在数组中的位置
			int index=0;
			//当2*key+2<num.length时表示有两个子孩子
			if(2*key+2<num.length){
				//当有两个子孩子时就找出具有最大键值的子孩子
				if(num[2*key+2]>num[2*key+1]){
					maxChild=num[2*key+2];
					index=2*key+2;
				}else{
					maxChild=num[2*key+1];
					index=2*key+1;
				}
				flag=true;
			}else if(2*key+1<num.length){//当2*key+1<num.length时表示有一个子孩子
				maxChild=num[2*key+1];
				index=2*key+1;
				flag=true;
			}
			//如果有子孩子就判断最大子孩子的值比当前节点值的大小
			if(flag){
				if(maxChild>num[key]){
					int temp=num[key];
					num[key]=num[index];
					num[index]=temp;
					key=index;
				}else{
					break;
				}
			}
			//h++表示下移一层
			h++;
		}
	}
}

    代码就只是一个简单的测试类了,只有几个方法实现上虑下虑操作,以前只是知道堆排序,从没有实现过,今天硬是鼓起勇气写了这个,还是能写出来的,所以如果有地方写得不怎么好的,希望各位多多指点。
  • 大小: 4.5 KB
1
0
分享到:
评论

相关推荐

    算法设计实验报告堆排序代码

    在实际应用中,可以考虑优化堆排序的实现,例如采用就地调整堆的方法减少空间消耗,或者结合其他排序算法(如快速排序)以提高特定情况下的性能。此外,理解并熟练掌握堆排序算法对于提升编程能力,尤其是处理大规模...

    数据结构课程设计 实验报告——堆排序

    堆排序是**就地排序**算法,只需要常数级别的额外空间,因此空间复杂度为\( O(1) \)。 #### 七、稳定性分析 堆排序是一种**不稳定**的排序方法。这意味着相同的关键字可能不会保持原有的相对顺序。 #### 八、算法...

    Python实现堆排序的方法详解

    这是因为堆排序是一种就地排序算法,只需要额外的常数个单元的空间用于存储临时变量。此外,由于每次比较和交换操作都是局部的,因此堆排序在实际应用中表现良好。 #### 五、应用场景 堆排序因其稳定的性能表现,在...

    Java堆排序算法详解

    "Java堆排序算法详解" Java堆排序算法是将原始数据转换为堆的形式,然后重复地删除堆顶元素,并将其插入到有序的序列中,以达到排序的目的。下面是Java堆排序算法的知识点总结: 1. heap的概念:堆是一种特殊的...

    八大排序.pdf

    选择排序、插入排序、希尔排序、归并排序、堆排序和计数排序这些算法各有特点,选择排序和插入排序的时间复杂度均为O(n²),适合较小规模的数据集。希尔排序是对插入排序的改进,它通过将原始数据分成若干子序列进行...

    十大经典排序算法.pdf

    十大经典排序算法是数据结构与算法领域中的基础,它们包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序和基数排序。这些算法分别适用于不同的场景,具有各自的时间复杂度...

    c语言经典排序算法(8种-含源代码)

    在堆结构的数组A中,堆的根节点为A[1],所以堆排序从A[n/2]开始,将每个非叶子节点进行下沉操作以确保每个子树都是一个合法的堆,然后再将根节点与最后一个元素交换,并排除最后一个元素,重复这个过程直到堆的大小...

    排序算法总结

    堆排序(Heap Sort)是一种基于二叉堆数据结构的排序算法,其思想是利用堆这种数据结构的特点进行排序。在建堆阶段,算法将输入数据构造为一个大顶堆或小顶堆,然后将堆顶元素(即最大或最小的元素)与堆的最后一个...

    计算机算法总结之排序

    堆排序是一种不稳定排序方法,但它能够就地排序,不需要额外的存储空间,时间复杂度为O(nlogn)。 线性复杂度排序方法是指排序的时间复杂度能够达到O(n)的排序算法,这样的算法并不多,且通常都有一定的限制条件。...

    数据结构排序PPT学习教案.pptx

    3. **选择排序**:例如简单选择排序和堆排序,通过选择当前未排序部分中的最小(大)元素并将其与未排序部分的第一个元素交换来实现排序。 4. **归并排序**:采用分治策略,将数据分成小段,分别排序后再合并,适用...

    PB15111604-金泽文-project11

    涉及的排序算法有直接插入排序、堆排序、归并排序和快速排序。其中,直接插入排序是最简单的基础算法,用于为其他算法提供框架。堆排序和快速排序的实现与教科书中的基本思路相似,但需要根据数组从0开始索引进行...

    c语言实例解析——数据结构篇(42-74)

    047 堆排序 048 归并排序 049 基数排序 050 二叉搜索树操作 051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双...

    常用sorting算法分析及java代码

    虽然与堆排序具有相同的运行时间,但归并排序在处理慢速存储介质时更为高效,例如磁带机。此外,归并排序是稳定的,适合处理链表,因为它可以在不增加额外空间的情况下实现。在某些编程语言中,如Perl 5.8之后的版本...

    数据结构最全源程序

    047 堆排序 048 归并排序 049 基数排序 050 二叉搜索树操作 051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双...

    排序问题和背包问题的求解

    用递归法实现快速排序。...通过将根节点元素与最后一个节点交换后,并删除最后一个元素,将最大元素确定,而交换后的堆破坏了堆的结构,通过上移下移操作调整堆的结构,并重复上述过程,对数组中的元素进行就地排序

    JavaScript实现的选择排序算法实例分析

    堆排序是就地排序,只需要常数级别的额外空间,但它是不稳定的排序算法,即相等元素的相对顺序可能会改变。 总的来说,选择排序适合小型数据集或对效率要求不高的场景,而堆排序和树形选择排序在处理大型数据时表现...

    chapter_12_排序和选择.zip

    6. 堆排序:利用堆这种数据结构实现排序,效率较高,且是原地排序,不需额外空间。 在实际应用中,Python还提供了Timsort,这是一种混合排序算法,结合了插入排序、归并排序和稳定的排序特性,表现优秀且适用于各种...

    C++直接插入排序详解以及代码实现

    需要注意的是,虽然直接插入排序简单且实现容易,但它在处理大规模数据或无序数据时效率较低,不如其他更高效的排序算法如快速排序、归并排序或堆排序。归并排序,作为一种基于分治策略的排序算法,具有稳定的O(n ...

    algoholics-anon:算法和数据结构

    演算法搜索: 二进制搜索( / ) 快速选择( ) 最短路径( )排序: 冒泡排序( ) 计数排序( / ) 堆排序( ) 插入排序( ) Knuth随机播放( ) 合并排序( ) 就地合并排序( ) quicksort( / / ) 基数排序...

    sort:对“模板” C中的例程实现进行排序

    您可以选择许多排序例程,包括: Timsort(稳定) 快速排序合并排序(稳定) 就地归并排序(不稳定) Shellsort 二进制插入排序堆排序选择排序(实际上仅是为了进行比较) 圣杯排序(稳定) 基于 。 感谢Andrey ...

Global site tag (gtag.js) - Google Analytics