`
大器晚成
  • 浏览: 52818 次
  • 性别: Icon_minigender_1
  • 来自: 厦门
社区版块
存档分类
最新评论

java写的堆排序 代码

阅读更多
参照改写自  http://blog.kingsamchen.com/archives/547#viewSource

public class HeapSorter {

	int temp = 0;

	/*
	 * 输 入: Ary(int[]) - [in,out]排序数组 nIndex(int) - 起始下标 nHeapSize(int) - 堆大小 输
	 * 出: - 功 能: 从nIndex开始检查并保持最大堆性质
	 */
	void MaxHeapify(int Ary[], int nIndex, int nHeapSize) {
		while (true) {
			int nL = left(nIndex);
			int nR = right(nIndex);
			int nLargest;

			if (nL <= nHeapSize && Ary[nIndex] < Ary[nL]) {
				nLargest = nL;
			} else {
				nLargest = nIndex;
			}

			if (nR <= nHeapSize && Ary[nLargest] < Ary[nR]) {
				nLargest = nR;
			}

			if (nLargest != nIndex) {
				// 调整后可能仍然违反堆性质
				swap(Ary, nLargest, nIndex);
				nIndex = nLargest;
			} else {
				break;
			}
		}
	}

	/*
	 * 输 入: Ary(int[]) - [in,out]排序数组 nHeapSize(int) - [in]堆大小(zero-based) 输 出:
	 * - 功 能: 将一个数组改造为最大堆
	 */
	void BuildMaxHeap(int Ary[], int nHeapSize) {
		for (int i = parent(nHeapSize); i >= 0; --i) {
			MaxHeapify(Ary, i, nHeapSize);
		}
	}

	/*
	 * 输 入: Ary(int[]) - [in,out]排序数组 nCount(int) - [in]元素个数 输 出: - 功 能:
	 * 对一个数组进行堆排序
	 */
	void HeapSort(int Ary[], int nCount) {
		int nHeapSize = nCount - 1;

		BuildMaxHeap(Ary, nHeapSize);

		for (int i = nHeapSize; i >= 1; --i) {
			swap(Ary, 0, i);
			--nHeapSize;
			MaxHeapify(Ary, 0, nHeapSize);
		}
	}

	private void swap(int[] array, int index1, int index2) {
		temp = array[index1];
		array[index1] = array[index2];
		array[index2] = temp;
	}

	private int left(int x) {
		return (x << 1) + 1;
	}

	private int right(int x) {
		return (x + 1) << 1;
	}

	private int parent(int x) {
		return ((x + 1) >> 1) - 1;
	}

	public static void main(String[] s) {
		int a[] = {6, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };
		new HeapSorter().HeapSort(a, 10);
		for (int i : a) {
			System.out.print(i + ",");
		}
	}
}

输出结果是:1,2,3,4,6,7,8,9,10,14,16,
未做优化.原文就不贴出了
0
1
分享到:
评论

相关推荐

    堆排序12.java 使用java代码实现

    堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用java代码实现堆排序12.java 使用...

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

    在这个主题中,我们将深入探讨堆排序的概念、工作原理以及如何用Java实现它。首先,我们需要理解堆是什么。 堆是一个近似完全二叉树的结构,并同时满足堆的性质:即父节点的键值或索引总是大于或小于(在最大堆和...

    Java 最大堆排序

    Java 写得最大堆排序代码,给大家参考下,自己刚写的。

    堆排序Java代码示例

    附件是堆排序Java代码示例,文件绿色安全,请大家放心下载,仅供交流学习使用,无任何商业目的! 堆排序是一种高效的比较类排序算法,它利用了二叉堆的数据结构来实现排序。堆排序可以分为两个主要步骤:建堆(将...

    堆排序 Java代码示例

    附件是堆排序Java代码示例,文件绿色安全,请大家放心下载,仅供交流学习使用,无任何商业目的! 堆排序是一种高效的比较类排序算法,它利用了二叉堆的数据结构来实现排序。堆排序可以分为两个主要步骤:建堆(将...

    Java实现堆排序.rar

    以下是一个简单的Java堆排序算法实现的伪代码: ```java class HeapSort { void heapify(int arr[], int n, int i) { // 代码实现下沉操作 } void swap(int arr[], int i, int j) { // 代码实现元素交换 } ...

    java堆排序

    #### 堆排序代码分析 提供的代码中定义了一个名为`HeapSort`的类,该类包含了主要的堆排序逻辑。`Sort`方法实现了堆排序的整体流程,`Adjust`方法负责维护最大堆的性质,`Display`方法用于输出数组状态。 #### 其他...

    java实现堆排序以及示例代码

    在Java中,我们可以使用以下步骤来实现堆排序: 1. **理解堆的概念**:堆是一个近似完全二叉树的结构,同时满足堆的性质,即每个节点的值都大于或等于其子节点的值(称为大顶堆,用于升序排列),或者小于或等于其...

    堆排序之Java实现

    以下是一个简单的Java代码示例,演示如何手动实现堆排序: ```java public class HeapSort { public void sort(int[] arr) { int n = arr.length; // 建堆 for (int i = n / 2 - 1; i &gt;= 0; i--) heapify(arr...

    堆排序JAVA实现代码

    以下将详细介绍堆排序的原理、步骤以及Java实现。 **堆排序的原理** 堆排序的核心思想是构建一个完全二叉树,即堆,然后通过调整堆结构,使得根节点(最大元素或最小元素)总能处于正确的位置。这个过程分为两个...

    Java实现堆排序算法(源代码)

    ### Java实现堆排序算法 #### 实现原理 堆排序是一种基于比较的排序算法,它主要依靠堆这种数据结构来进行操作。堆是一种特殊的完全二叉树结构,其中每个节点的值都大于等于(对于大顶堆)或小于等于(对于小顶堆...

    [Java算法-排序]-堆排序.java

    此外,文档还包括一个逐步指南,介绍了如何在Java中实现堆排序,包括详细的代码示例和实现细节。 文档还涵盖了高级主题,如如何优化代码以提高性能以及如何处理大的数组。该资源包括实用练习,让读者可以练习在Java...

    堆排序代码

    ### 堆排序原理与实现 #### 一、堆排序简介 堆排序是一种基于比较的排序算法,利用了堆的数据结构。它将待排序数组构造成一个大顶堆(或小顶堆...通过上述代码实现,可以有效地理解和掌握堆排序的工作原理及实现细节。

    Java实现堆排序

    在`HeapButtonUp.java`这个文件中,我们可以预期代码会包含一个方法,用于执行上述堆排序的步骤。可能的实现包括: ```java public class HeapSort { public static void heapify(int[] arr, int n, int i) { // ...

    java实现的shell排序快速排序归并排序堆排序

    本篇将详细介绍标题所提及的四种排序算法:Shell排序、快速排序、归并排序以及堆排序。 1. **Shell排序**: Shell排序是一种改进的插入排序,由Donald Shell于1959年提出。它通过设置一个间隔序列,使得数组中的...

    Java各种排序算法代码.zip

    Java的PriorityQueue类可以用来实现堆排序的一部分功能。 7. 计数排序(Counting Sort)、桶排序(Bucket Sort)和基数排序(Radix Sort): 这些排序算法适用于特定类型的数据,例如非负整数。计数排序统计每个...

    Java各种排序算法代码.

    7. **堆排序**:基于完全二叉树的堆数据结构,通过构建大顶堆或小顶堆进行排序。堆排序在原地进行,无需额外空间,但效率低于快速排序。 8. **计数排序**:非基于比较的排序,适用于整数排序,统计每个元素出现的...

    java实现的堆排序 含代码说明和示例.docx

    堆排序 java实现的堆排序 含代码说明和示例

    Java学习代码-堆排序

    JavaSE…… Java JavaEE : javaIO, /Socket JDBCTomcat/Servlet, 堆排序 堆排序 堆排序 堆排序 堆排序

Global site tag (gtag.js) - Google Analytics