`
cooliufang
  • 浏览: 129879 次
社区版块
存档分类
最新评论

Java排序算法之 —— 堆排序

阅读更多
package algorithm.sort;

/**
 * 堆排序算法:首先建立最大堆,因为最大元素在根A[0],所以将其与最后一个元素交换
 * 然后去除最后一个节点,重新调整最大堆,循环此过程
 * @author Administrator
 *
 */
public class HeapSort {
	
	//堆排序
	public void heapSort(int[] a) {
		int heapSize =  a.length;
		//建立最大堆
		buildMaxHeap(a, heapSize);
		//从最后一个元素开始循环
		for (int i = a.length-1; i > 0; i--) {
			//交换最大元素与最后一个元素
			exchange(a, i, 0);
			//重新调整根节点为最大堆
			keepMaxHeapify(a, 0, --heapSize);
		}
		
	}
	
	//给定一个数组,建立最大堆
	public void buildMaxHeap(int[] a, int heapSize) {
		//对数中每一个不是叶节点的节点调用
		for (int i = heapSize/2; i>=0; i--) {
			keepMaxHeapify(a, i, heapSize);
//			keepMaxHeapifyNoRecurisive(a, i, heapSize);
		}
	}
	
	//保持最大堆性质,使以i为根的子树为最大堆(采用递归方法)
	public void keepMaxHeapify(int[] a, int i, int heapSize) {
		int left = left(i);
		int right = right(i);
		
		int largest = i;
		if (left < heapSize && a[left] > a[i]) {
			largest = left;
		}		
		if (right < heapSize && a[right] > a[largest]) {
			largest = right;
		}
		
		if (largest != i) {
			exchange(a, largest, i);
			keepMaxHeapify(a, largest, heapSize);
		}
	}
	
	//非递归方法保持最大堆性质
	public void keepMaxHeapifyNoRecurisive(int[] a, int i, int heapSize) {		
		int largest = i;
		
		while (largest < heapSize) {
			int left = left(i);
			int right = right(i);
			if (left < heapSize && a[left] > a[i]) {
				largest = left;
			}			
			if (right < heapSize && a[right] > a[largest]) {
				largest = right;
			}
			
			if (largest == i) break;
			exchange(a, largest, i);
			i = largest;
		}
	}
	//父节点(考虑java中下标从0开始)
	public int parent(int i) {
//		return (i-1) / 2;
		return (i-1) >> 1;	//二进制计算法
	}
	
	//左孩子
	public int left(int i) {
//		return i * 2 + 1;
		return (i << 1)+1;
	}
	
	//右孩子
	public int right(int i) {
//		return (i + 1) * 2;
		return (i + 1) << 1;
	}
	
	//交换元素
	public void exchange(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
	//打印数组
	public void printArr(String str, int[] a) {
		System.out.print(str + "\t");
		for(int i = 0; i < a.length; i++)
			System.out.print(a[i] + " ");
		System.out.println();
	}
	
	//测试数组
	public static void main(String[] args) {
		int[] a = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};

		HeapSort hs = new HeapSort();
		
		hs.printArr("原始数组为:", a);
		hs.buildMaxHeap(a, a.length);
		hs.printArr("建立最大堆为:", a);
		hs.heapSort(a);
		hs.printArr("堆排序后为:", a);

	}

}



//output~
原始数组为: 4 1 3 2 16 9 10 14 8 7
建立最大堆为: 16 14 10 8 7 9 3 2 4 1
堆排序后为: 1 2 3 4 7 8 9 10 14 16
分享到:
评论

相关推荐

    java语言排序——选择排序法和冒泡排序法(排序时间的测试盒比较)

    在实际应用中,我们通常会使用更高效的排序算法,如快速排序、归并排序或堆排序等,它们在大多数情况下都能提供更好的性能。不过,了解基础的排序算法如选择排序和冒泡排序,对于学习和理解更复杂的算法至关重要。 ...

    算法可视化系列——排序算法——选择排序

    **选择排序**是一种简单直观的排序算法,它的工作原理如下:...在实际应用中,更高效的排序算法如快速排序、归并排序或堆排序等通常会优先考虑。然而,对于教学和理解排序算法的基本原理,选择排序是一个很好的起点。

    java面试java排序算法

    在Java面试中,排序算法是常见的话题,因为它在实际编程中有着广泛的应用。这里我们将讨论两种常见的排序算法:归并排序和堆排序。 首先,让我们深入理解归并排序(Merge Sort)。归并排序是一种分治策略,其基本...

    Java经典算法50题——答案下载!

    1. 排序算法:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等,理解每种排序算法的工作原理和时间复杂度是至关重要的。 2. 搜索算法:线性搜索、二分搜索、深度优先搜索(DFS)、广度优先搜索...

    Java数据结构和算法

    (1)数据结构与算法概念...(15)排序算法(五)——快速排序 (16)排序算法(六)——希尔排序 (17)排序算法(七)——堆排序 (18)排序算法(八)——基数排序 (19)排序算法(九)——八大排序算法总结

    数据结构与算法分析——Java语言描述

    常见的排序算法(如冒泡排序、快速排序、归并排序、堆排序)和查找算法(如线性查找、二分查找)都有详尽的解释和实例。此外,还包括动态规划、贪心算法、回溯法等高级算法思想。算法分析不仅关注实现,更强调时间...

    选择排序算法。其中堆排序使用的时最小堆,通过改变数组下标变更堆的顶实现的

    本文将深入探讨两种特定的排序算法——选择排序和堆排序,并重点解析堆排序如何利用最小堆来实现排序过程。这两种算法在Java编程语言中都有广泛应用。 首先,我们来看选择排序。它是一种简单直观的排序算法,其基本...

    数据结构与算法答案——java语言描述

    5. **排序算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。Java的`Collections.sort()`方法使用了高效的排序算法,如TimSort,了解这些算法的原理有助于编写高性能的代码。 6. **图与树*...

    数据结构与算法分析——Java语言描述-带书签目录高清扫描版

    排序算法如冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序,各有优缺点,适用于不同的数据特性。查找算法包括顺序查找、二分查找和哈希查找,其中哈希表提供了近乎常数时间的查找效率。此外,高级算法如...

    最快的排序算法 图解八大排序算法——我见过的最详细的讲解(转),排序算法数据结构

    常见的排序算法有八种,即选择排序、冒泡排序、插入排序、归并排序、快速排序、堆排序、.radix 排序和基数排序。 一、分类 内部排序和外部排序是两种基本的排序分类。内部排序是指待排序记录存放在计算机随机...

    排序算法 Java经典算法

    学习和掌握这些经典的Java排序算法,不仅能提升你的编程技能,还能帮助你在面对不同场景和数据规模时,选择最合适的排序方法,从而提高程序的运行效率。无论是理论学习还是实际开发,这些知识都将是你宝贵的财富。

    各种排序算法java实现

    标题 "各种排序算法java实现" 涉及到的是计算机科学中的一个重要领域——算法,特别是排序算法在Java编程语言中的具体应用。排序算法是数据结构与算法分析中的基础部分,它们用于将一组数据按照特定顺序排列。在这个...

    《Java数据结构和算法》学习笔记(2)——4种简单排序算法

    在实际开发中,我们往往使用更高效的排序算法,如快速排序、归并排序、堆排序等。然而,了解并能实现这些基础排序算法,对于提升编程思维和问题解决能力大有裨益。在学习和研究过程中,可以结合工具,例如使用Java...

    常用排序算法小结(附Java实现)

    文章可能涵盖了如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等多种经典的排序算法,并且通过Java代码进行了详尽的解释和实现。 1. 冒泡排序:这是一种简单的排序方法,通过重复遍历数组,比较相邻...

    java中和排序算法

    ### Java中的排序算法详解 #### 一、排序算法的分类 根据给定文件中的描述,Java中的排序算法大致可以分为以下几类: 1. **插入排序**:包括直接插入排序、折半插入排序、希尔排序等。 2. **交换排序**:主要包括...

    java实现各种排序算法及其速度对比(附详细代码)(csdn)————程序.pdf

    冒泡排序是最简单的排序算法之一,通过重复遍历待排序的序列,每次比较相邻元素并交换,如果前面的元素大于后面的元素,就交换它们的位置。这个过程会一直重复,直到没有更多的交换发生,即序列已经排序完成。冒泡...

    容易理解的堆排序代码(JAVA)

    这个简单的Java实现展示了堆排序的基本思想,它的时间复杂度为O(n log n),空间复杂度为O(1),是原地排序算法。由于其效率和不需要额外存储空间的特点,堆排序在处理大数据量时非常有用。然而,对于小规模数据或近乎...

    Java常见排序算法

    冒泡排序是最基础的排序算法之一,通过不断地交换相邻的不正确顺序的元素来逐步完成排序。它的主要思想是重复地遍历待排序的序列,每次比较两个元素,如果它们的顺序错误就把它们交换过来。 2. **选择排序** ...

Global site tag (gtag.js) - Google Analytics