package com.sort;
public class HeapSort {
/**
* 将整棵树构建为最大堆
* @param a
*/
public void builMaxHeap(int[] a){
int length = a.length-1;//堆排序数据长度,第一个数据不使用,设置为0,哨兵值
int heapSize = length/2;
for(;heapSize > 0 ;heapSize--){
maxHeapfy(a,heapSize);
}
}
/**
* 将子树构建为最大堆
* @param a
* @param root
*/
public void maxHeapfy(int[] a,int root){
int largest = root;
int left = 2*largest;
int right = 2*largest +1;
if(left>a.length-1){//当左子树大于数组最后一个元素的下标时,直接返回
return;
}else if(left == a.length-1){//当左子树等于数组最后一个元素的下标时,比较数组
if(a[root]<a[left]){
int tmp = a[root];
a[root] = a[left];
a[left]= tmp;
}
return;
}
//其他情况则表示存在右节点,按照一颗完整子树去比较根节点与左右子树的大小
if(a[largest]<a[left]){
largest = left;
}
if(a[largest]<a[right]){
largest = right;
}
if(root != largest){//保持树中的根节点为最大值
int tmp;
tmp = a[root];
a[root] = a[largest];
a[largest] = tmp;
}else if(root == largest){//如果根节点为最大值
if(a[left]>a[right]){//比较左右子树的大小
largest = left;
}else{
largest = right;
}
}
//largest = largest + 1;
maxHeapfy(a,largest);
}
/**
* 堆排序算法
* @param a
* @return
*/
public int[] heapSort(int[] a){
this.builMaxHeap(a);
int length = a.length-1;
int[] b = new int[a.length];
b[0] = -1;//哨兵值,这个树不参与排序,和a数组中第一个值保持一致
for(int i=length;i>0;i--){//循环将树重新构建成最大堆
b[i] = a[1];//将新构建的最大堆中根节点赋值给数组b
a[1] = -1;//将根节点赋值无用的-1标记
this.maxHeapfy(a, 1);//重新构建堆
}
return b;
}
public static void main(String[] args) {
int[] a = new int[]{-1,4,1,3,2,16,22,23,0,25,25,25,9,10,14,8,1000};
HeapSort heapSort = new HeapSort();
int[] b = heapSort.heapSort(a);
for(Integer sortHeap:b){
System.out.println(sortHeap);
}
}
}
分享到:
相关推荐
经典排序算法 - 堆排序Heap sort序 经典排序算法 - 地精排序Gnome Sort 经典排序算法 - 奇偶排序Odd-even sort 经典排序算法 - 梳排序Comb sort 经典排序算法 - 耐心排序Patience Sorting 经典排序算法 - 珠...
python python_十大排序算法实现之堆排序
该资源提供了Java中实现堆排序的全面指南。文档中涵盖了堆排序的基本概念,包括如何对数组进行排序以及如何在Java中实现堆排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现堆排序,包括详细的代码示例和...
在C++中实现堆排序,我们可以使用标准库中的`<algorithm>`,但为了更好地理解算法原理,通常会手动实现堆操作。以下是堆排序的基本步骤: 1. **建立堆**:遍历数组,从最后一个非叶子节点开始,对每个节点执行下沉...
在上面的代码中,我们使用 Java 语言实现了堆排序算法。其中,Heap 类中包括两个函数:heapSort 和 heapify。heapSort 函数接受一个整数数组作为输入,并使用堆排序算法对该数组进行排序。heapify 函数用于对一个...
简单的堆排序算法:以定长数组为例,动态数组等可以以此类推
主要是对算法导论中堆排序的实现
本文将深入探讨四种在C++中实现的常见排序算法:插入排序、冒泡排序、堆排序和快速排序。这些算法各有特点,适用于不同的场景,理解并掌握它们对于提升编程能力至关重要。 1. **插入排序**: 插入排序是一种简单的...
通过学习和完成这个练习,读者将能够掌握堆排序算法的思想和实现过程,并了解其在排序算法中的应用。此外,文档还提供了练习题和答案,帮助读者巩固所学知识并检查自己的理解。 无论您是C++编程的初学者还是有一定...
堆排序是一种基于比较的排序算法,它利用了数据结构中的“堆”这一概念。在计算机科学中,堆是一个近似完全二叉树的结构,并同时满足堆的...理解和掌握堆排序的原理和实现方法对于学习算法和提升编程能力具有重要意义。
在VC++环境中实现堆排序,你需要使用C++的基本数据结构和算法库。你可以创建一个通用的函数,接受一个可迭代的数据容器(如std::vector),然后利用指针或者迭代器来操作元素,构建和调整堆。同时,VC++提供了STL...
堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和...
本书第三部分专注于介绍各种排序算法,包括冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序等。作者不仅分析了每种排序算法的原理,还比较了它们的效率和适用场景,帮助程序员在实际编程中作出恰当的选择...
C语言实现的堆排序算法。 提供了堆排序算法的一个接口,可以为其它功能提供功能。
本主题将深入探讨四种常见的排序算法:堆排序、快速排序以及两种未在标题中明确提到但同样重要的排序方法——基数排序和计数排序。 首先,让我们详细了解一下堆排序。堆排序是一种基于比较的排序算法,利用了数据...
以下是一个简单的C++实现堆排序的例子: ```cpp #include using namespace std; void heapify(int arr[], int n, int i) { int largest = i; // 初始化最大值为根节点 int left = 2 * i + 1; int right = 2 * ...
1、 实现堆排序算法。 2、 理论分析并实验验证堆排序算法的时间复杂度。
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...
本资源提供了七大经典排序算法的实现程序,包括快速排序、冒泡排序、选择排序、归并排序、插入排序、希尔排序和堆排序。下面将逐一详细介绍这些排序算法及其原理。 1. 快速排序:由C.A.R. Hoare提出,是一种采用...