在堆排序中,把待排序的文件逻辑上看作是一棵顺序二叉树,
堆是一个具有这样性质的顺序二叉树,每个非终端结点(记录)的关键字大于等于它的孩子结点的关键字。
显然,在一个堆中,根结点具有最大值(指关键字,下同),而且堆中任何一个结点的非空左、右子树都是一个堆,它的根结点到任一叶子的每条路径上的结点都是递减有序的。
堆排序的基本思想是:首先把待排序的顺序表示(一维数组)的文件(R1,R2,…,Rn)在概念上看作一棵顺序二叉树,并将它转换成一个堆。这时,根结点具有最大值,删去根结点,然后将剩下的结点重新调整为一个堆。反复进行下去,直到只剩下一个结点为止。
堆排序的关键步骤是如何把一棵顺序二叉树调整为一个堆。初始状态时,结点是随机排列的,需要经过多次调整才能把它转换成一个堆,这个堆叫做初始堆。建成堆之后,交换根结点和堆的最后一个结点的位置,同时,剩下的结点(除原堆中的根结点)又构成一棵顺序二叉树。
这时,根结点的左、右子树显然仍都是一个堆,它们的根结点具有最大值(除上面删去的原堆中的根结点)。把这样一棵左、右子树均是堆的顺序二叉树调整为新堆,是很容易实现的。
堆排序中调整堆的伪代码如下:
void adjust(struct node r[m+1],int m)
/* 将文件(r[1],r[2],…,r[m])解释为一棵顺序二叉树,将其中以r[i]为根结点的二叉树调整
为一个堆,设以r[i]为根的二叉树的左,右子树已是堆,1≤i≤1[m/2] */
{ x=r[i];j=2*i; /*求出r[i]的左孩子r[2*i],即r[j] */
while (j<=m) /*有左孩子*/
{ if ((j<m) &&(r[j].key<r[j+1].key)) /*比较左、右孩子*/
j=j+1; /*左孩子<右孩子*/
if (x.key<r[j].key) /*比较根结点和它的大孩子*/
{ r[i]=r[j]; /*大孩子上移到它的双亲位置*/
i=j; /*今 r[j]为根结点*/
j=2*i; /*求出左孩子*/
}
else j=m+1 /*根不小于它的任一孩子时,强迫退出while循环*/
}
r[i]:=x; /*将存放在x中的根结点放到r[i]中*/
}
========================
以下为Java代码实现的堆排序程序代码:
public class HeapSort2 {
public void HeapAdjust(int array[], int i, int nLength)
{
int nChild, nTemp;
//数组0为下标的话 2*i+1表示左子树根节点 2*i+2表示右子树根节点
for (nTemp = array[i]; 2 * i + 1 < nLength; i = nChild)
{
// 子结点的位置是 父结点位置 * 2 + 1
nChild = 2 * i + 1;
// 得到子结点中较大的结点
if (nChild != nLength - 1 && array[nChild + 1] > array[nChild])
++nChild;
// 如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点
if (nTemp < array[nChild])
{
array[i] = array[nChild];
}
else // 否则退出循环
{
break;
}
}
// 最后把需要调整的元素值放到合适的位置
array[i] = nTemp;
}
// 堆排序算法
public void HeapSort(int array[], int length)
{
// 调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素
for (int i = length / 2 - 1; i >= 0; --i)
{
HeapAdjust(array, i, length);
}
// 从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素
int t=0;
for (int i = length - 1; i > 0; --i)
{
// 把第一个元素和当前的最后一个元素交换,
// 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
t=array[0];
array[0]=array[i];
array[i]=t;
//Swap(&array[0], &array[i]);
// 不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值
HeapAdjust(array, 0, i);
}
}
public static void main(String[] args)
{
HeapSort2 hs=new HeapSort2();
int arr[]=new int[]{12,91,3,66,79,32,55};
hs.HeapSort(arr, arr.length);
for(int i=0;i<arr.length;i++)
{
System.out.println(arr[i]);
}
}
}
分享到:
相关推荐
堆排序详细图解(通俗易懂)+排序算法----堆排序(超详细)堆排序详细图解(通俗易懂)+排序算法----堆排序(超详细)堆排序详细图解(通俗易懂)+排序算法----堆排序(超详细)堆排序详细图解(通俗易懂)+排序算法...
在实际应用中,快速排序的平均情况是最快的,但是堆排序的最坏情况是 O(nlogn) 的,这说明堆排序的时间复杂度是渐进最优的。但是,快速排序的实际执行时间却比堆排序更快,这是因为快速排序的 cache freundliness 比...
堆排序是一种基于比较的排序算法,它利用了数据结构中的“堆”这一概念。在计算机科学中,堆是一个近似完全二叉树的结构,并同时满足堆的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。堆排序有两种...
堆排序----堆与堆排序10-从堆的定义可以看出,堆实质是满足如下性质的完全二叉树:二叉树中任一非叶子结点均小于(大于)它的孩子结点
常用的排序算法--堆排序,通过创建堆的方法进行排序
本主题主要探讨了三种经典的排序算法——希尔排序、快速排序和堆排序,并在Java语言环境下通过多线程实现,以充分利用系统资源,提升排序性能。 希尔排序是一种基于插入排序的算法,由Donald Shell于1959年提出。它...
堆排序是一种基于比较的排序算法,它利用了数据结构中的“堆”这一概念。在计算机科学中,堆通常被理解为一个完全二叉树,其中每个父节点的值都大于或等于(最大堆)或小于或等于(最小堆)其子节点的值。堆排序分为...
堆排序--大顶堆排序 大顶堆排序是堆排序的一种,通过构建大顶堆来实现排序的过程。下面是对大顶堆排序的详细解释: 什么是大顶堆? 大顶堆是一种特殊的完全二叉树,它满足以下条件: * 对于每个非叶子节点,节点...
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
堆排序-flash演示 可自己输入数据............
堆排序是一种基于比较的排序算法,它通过构建和维护一个最大堆或最小堆来实现排序。在C语言中,我们可以自定义函数来实现这个过程。下面是对标题和描述中涉及的堆排序知识点的详细说明: 1. **最大堆**:在堆排序中...
堆排序是一种基于比较的排序算法,它通过构建一个大顶堆或小顶堆来实现排序。在计算机科学中,堆通常被理解为一种特殊的树形数据结构,满足堆的性质:父节点的值总是大于或等于(对于大顶堆)或小于或等于(对于小...
8. 堆排序(Heap Sort):堆排序利用了堆这种数据结构,构建一个大顶堆或小顶堆,然后将堆顶元素与末尾元素交换,调整堆,再将末尾元素移除,重复这个过程。时间复杂度为O(n log n)。 这些排序算法的Swift实现提供...
堆排序是一种基于比较的排序算法,它利用了数据结构中的“堆”这一概念。在计算机科学中,堆是一个近似完全二叉树的结构,并同时满足堆的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。堆排序有两种...
Python 堆排序 堆排序 堆排序 堆排序 堆排序
堆排序算法详解 堆排序是一种树形选择排序算法,它的基本思想是将待排序的数组构建成一个大根堆(或小根堆),然后将堆顶元素与堆底元素交换位置,再将剩余元素重新构建成堆,重复执行交换和重构堆的操作,直到整个...
该资源提供了Java中实现堆排序的全面指南。文档中涵盖了堆排序的基本概念,包括如何对数组进行排序以及如何在Java中实现堆排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现堆排序,包括详细的代码示例和...
堆排序 堆排序 堆排序 堆排序 堆排序
各种排序算法,包括希尔算法,快速排序,堆排序-A variety of sorting algorithms, including the Hill algorithm, quick sort, heap sort
堆排序