堆排序在最坏的情况下,其时间复杂度也能达到O(nlogn)。相对于快速排序来说,
这是它最大的优点,此外,堆排序仅需要一个记录大小供交换用的辅助存储空间。
堆排序的数据结构是二叉堆,二叉堆的特点有两个,一个是它是一棵完全二叉树,
另一个是它的根结点小于孩子结点,所以我们很容易找到它的最小结点----根结点;当然
如果你想找到最大结点的话,那就要扫描所有的叶子结点,这是很费时间的,如果你想找的
是最大结点的话,你最好把它弄成一个大顶堆,即一棵根结点大于孩子结点的完全二叉树。
二叉堆通常用数组来实现,它舍弃下标0,从下标1开始置数,则很容易满足,对于数组
中任意位置i上的元素,其左儿子的位置在2i上,右儿子的位置在2i+1上,双亲的位置则在
i/2上。
堆排序的算法之一是把数组构建成二叉堆----这只要增添一个长度为n+1的辅助空间,
然后把原数组的元素依次插入到二叉堆即可。然后删除二叉堆的根,把它作为排序后的数组
的第一个元素,然后使二叉堆的长度减1,并通过上移使得新得到的序列仍为二叉堆,
再提取新二叉堆的第一个元素到新数组。依此类推,直到提取最后一个元素,
新得到的数组就是排序后的数组。
template <class T>
void Insert(T a[], int len, T x)//把x插入到原长度为len的二叉堆,注意保证新二叉堆不越界
{
int i;
for (i=len; i/2>0 && a[i/2]>x; i/=2)
a[i] = a[i/2];
a[i] = x;
}
template <class T>
T DeleteMin(T a[], int len)//删除二叉堆的根,并通过上移使得新得到的序列仍为二叉堆
{
if (len == 0)
exit(1);
T min = a[1];//二叉堆的根
T last = a[len--];//二叉堆的最后一个元素
int c;
int i;
for (i=1; i*2<=len; i=c)//把二叉堆的某些元素往前移,使得新得到的序列仍为二叉堆
{
c = i * 2;//i的左儿子
if (c != len && a[c+1] < a[c])//若i有右儿子,且右儿子小于左儿子,c指向右儿子
c++;
if (last > a[c])//若i的小儿子小于二叉堆的最后一个元素,把其移到i的位置
a[i] = a[c];
else
break;
}
a[i] = last; //把二叉堆的最后一个元素放到适当的空位,此时得到的序列仍为二叉堆
return min;
}
template <class T>
void HeapSort(T a[], int len)
{
T *ca = new T[len+1]; //复制原数组到二叉堆
ca[0] = 0;
for (int i=0; i<len; i++) //把元素依次插入到二叉堆
Insert(ca, i+1, a[i]);
for (int i=0; i<len; i++)//依次提取二叉堆的根作为排序后的数组的元素
{
a[i] = DeleteMin(ca, len-i);
}
a[len-1] = ca[1]; //注意不能忘了最后一个元素
delete []ca;
}
在《数据结构习题与解析》(李春葆 编著 清华大学出版社)中看到一个类似的算法,
它是把原数组构建成一个大顶堆,然后把大顶堆的第一个元素与最后一个元素交换;
再把前n-1个元素重新构造成一个大顶堆,把新大顶堆的第一个元素与最后一个元素交换;
依此类推,直到新大顶堆只有一个元素,这样就得到了一个有序的二叉堆。
算法如下:
template <class T>
void HeapSort(T a[], int len)
{
T *ca = new T[len+1];
ca[0] = 0;
for (int i=0; i<len; i++)
ca[i+1] = a[i];
for (int i=len/2; i>0; i--) //建立初始堆
HeapAdjust(ca, len, i);
for (int i=len; i>1; i--)//进行len-1次循环,完成堆排序
{
Swap(ca[1], ca[i]); //新大顶堆的第一个元素与最后一个元素交换
HeapAdjust(ca, i-1, 1);//筛a[1]元素,得到i-1个元素的堆
}
for (int i=0; i<len; i++)
a[i] = ca[i+1];
delete []ca;
}
template <class T>
void HeapAdjust(T a[], int len, int left) //将i与其小儿子交换位置
{
if (len == 0)
exit(1);
T x = a[left];
int i = left;
int c = 2 * i;
while (c <= len)
{
if (c < len && a[c+1] > a[c])//若i有右儿子,且右儿子大于左儿子,c指向右儿子
c++;
if (last < a[c])//若i的大儿子大于二叉堆的最后一个元素,把其移到i的位置
{
a[i] = a[c];
i = c;
c = 2 * i;
}
else
break;
}
a[i] = x; //把原二叉堆的第一个元素放到适当的空位
}
template <class T>
void Swap(T & a, T & b)
{
T t = a;
a = b;
b = t;
}
还有一种方法是每次都要重新调整大顶堆,使得父亲比儿子大,这样调整的函数较简单,
但因为每次都要遍历一半的元素,时间复杂度较大。
算法如下:
template <class T>
void HeapSort(T a[], int len)
{
T *ca = new T[len+1];
ca[0] = 0;
for (int i=0; i<len; i++)
ca[i+1] = a[i];
for (int i=len/2; i>0; i--) //把原数组构建成一个大顶堆
HeapAdjust(ca, len, i);
Swap(ca[1], ca[len]); //把大顶堆的第一个元素与最后一个元素交换
for (int i=len-1; i>0; i--)
{
for (int j=i/2; j>0; j--)//遍历长度为i的堆,得到新的大顶堆
HeapAdjust(ca, i, j);
Swap(ca[1], ca[i]);
}
for (int i=0; i<len; i++)
a[i] = ca[i+1];
delete []ca;
}
template <class T>
void HeapAdjust(T a[], int len, int i) //将i与其小儿子交换位置
{
int c = 2 * i;
if (c < len)
{
T & max = (a[c] > a[c+1])? a[c] : a[c+1];
if (a[i] < max)
Swap(a[i], max);
}
else
{
if (a[i] < a[c])
Swap(a[i], a[c]);
}
}
template <class T>
void Swap(T & a, T & b)
{
T t = a;
a = b;
b = t;
}
模仿构造大顶堆的方法,我们可以调用HeapAdjust()构造一个二叉堆,并提取二叉堆的根到新数组,
然后把原二叉堆的最后一个元素放到根的位置,再调用HeapAdjust()构造一个新二叉堆,依此类推。
算法如下:
template <class T>
void HeapSort(T a[], int len)
{
T *ca = new T[len+1];
ca[0] = 0;
for (int i=0; i<len; i++)
ca[i+1] = a[i];
for (int i=len/2; i>0; i--) //把原数组构建成一个大顶堆
HeapAdjust(ca, len, i);
a[0] = ca[1];
ca[1] = ca[len]; //把二叉堆的最后一个元素放到根的位置
for (int i=len-1; i>0; i--)
{
for (int j=i/2; j>0; j--)
HeapAdjust(ca, i, j);
a[len-i] = ca[1];
ca[1] = ca[i]; //把二叉堆的最后一个元素放到根的位置
}
delete []ca;
}
template <class T>
void HeapAdjust(T a[], int len, int i)
{
int c = 2 * i;
if (c < len)
{
T & min = (a[c] < a[c+1])? a[c] : a[c+1];
if (a[i] > min)
Swap(a[i], min);
}
else
{
if (a[i] > a[c])
Swap(a[i], a[c]);
}
}
template <class T>
void Swap(T & a, T & b)
{
T t = a;
a = b;
b = t;
}
后面两种方法采用的是递归,容易理解,但时间复杂度较高,因为比前两种要慢上很多,
所以不可能是O(nlogn),估计是O(n^2),但具体我也不会算,请。
相关推荐
堆排序是一种基于比较的排序算法,它通过构造一个近似完全二叉树的堆...结合《算法导论》的理论,我们可以用VC6.0这样的开发环境编写和测试代码,理解堆排序的实现细节,并从中学习到如何在实际问题中运用这一算法。
简单的堆排序算法:以定长数组为例,动态数组等可以以此类推
一个堆排序算法 c++写的 逻辑相同 可自行 改为java 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一个堆排序算法 c++ 写一...
C语言实现的堆排序算法。 提供了堆排序算法的一个接口,可以为其它功能提供功能。
堆排序算法 java
堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和Python分别实现堆排序算法; 堆排序:应用Java和...
java的堆排序算法实现程序,含测试,可直接运行。java的堆排序算法实现程序,含测试,可直接运行。
堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在本场景中,我们关注的是堆排序的源代码,它适用于openSUSE 11.4操作系统,并且是使用GCC version 4.5.1编译器编译的。在这个名为"sort...
堆排序是一种基于比较的排序算法,它通过构造一个完全二叉树(称为“堆”)来实现排序。在计算机科学中,堆是一个可以被看作是完全二叉树的...理解和掌握堆排序不仅有助于提升编程能力,也有助于解决更复杂的算法问题。
堆排序是一种基于比较的排序算法,它通过构造一个大顶堆或小顶堆来实现排序。在大顶堆中,每个父节点的值都大于或等于其子节点的值;在小顶堆中,父节点的值小于或等于子节点的值。这种数据结构类似于一个完全二叉树...
本主题将深入探讨四种常见的排序算法:堆排序、快速排序以及两种未在标题中明确提到但同样重要的排序方法——基数排序和计数排序。 首先,让我们详细了解一下堆排序。堆排序是一种基于比较的排序算法,利用了数据...
此外,理解并熟练掌握堆排序算法对于提升编程能力,尤其是处理大规模数据的排序问题,具有重要意义。 附录中的代码分别实现了模式计算和堆排序的功能。模式计算用于找出数组中出现次数最多的元素,而堆排序部分则...
总的来说,这个C语言实现的堆排序算法不仅涉及到了排序算法的基本原理,还涵盖了C语言的基础知识,对于理解和掌握这两种技术都有很大帮助。通过阅读和分析源代码,我们可以深入理解堆排序的工作机制,同时提高C语言...
本篇文章将详细介绍如何使用C语言实现堆排序算法,并通过代码示例深入理解其工作原理。 #### 堆排序算法原理 在堆排序中,首先需要构建一个大顶堆(或小顶堆),然后将堆顶元素与堆尾元素交换,将最大的元素“沉”...
最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法最优堆排序算法
通过具体的例子验证算法的正确性,并提供详细的注释说明,有助于其他开发者理解和学习堆排序算法的实现原理。 堆排序算法的效率依赖于树的高度,由于堆是完全二叉树,它的高度大约是logn。因此,堆排序的性能不会...
本文将深入探讨四种在C++中实现的常见排序算法:插入排序、冒泡排序、堆排序和快速排序。这些算法各有特点,适用于不同的场景,理解并掌握它们对于提升编程能力至关重要。 1. **插入排序**: 插入排序是一种简单的...
算法设计课程中的最小堆排序算法实现,windows下实现。
标签" c++ 排序算法"明确了主题,暗示我们将深入理解C++如何处理排序问题,特别是堆排序这一特定算法。 现在,让我们详细探讨堆排序的原理和C++实现: 1. **堆的构建**:首先,我们需要将无序的数组构建成一个大...
内容概要:本文详细介绍了堆排序算法的基础概念、工作原理、性能特点...其他说明:本文不仅适用于理解和掌握堆排序算法本身,还涵盖了相关的重要概念,如堆化、稳定性、时间复杂度等,有助于全面理解和运用堆排序算法。