堆排序:堆排序算法

堆排序在最坏情况下其时间复杂度也能达到O(nlogn)相对于快速排序来说
这是它最大优点此外堆排序仅需要个记录大小供交换用辅助存储空间
堆排序数据结构是 2叉堆 2叉堆特点有两个个是它是棵完全 2叉树另个是它根结点小于孩子结点所以我们很容易找到它最小结点----根结点；当然如果你想找到最大结点话那就要扫描所有叶子结点这是很费时间如果你想找是最大结点话你最好把它弄成个大顶堆即棵根结点大于孩子结点完全 2叉树
2叉堆通常用来实现它舍弃下标0从下标1开始置数则很容易满足对于中任意位置i上元素其左儿子位置在2i上右儿子位置在2i+1上双亲位置则在i/2上
堆排序算法的是把构建成 2叉堆----这只要增添个长度为n+1辅助空间然后把原元素依次插入到 2叉堆即可然后删除 2叉堆根把它作为排序后第个元素,然后使 2叉堆长度减1并通过上移使得新得到序列仍为 2叉堆再提取新 2叉堆第个元素到新依此类推直到提取最后个元素新得到就是排序后
template<T>
voidInsert(Ta,len,Tx)//把x插入到原长度为len 2叉堆注意保证新 2叉堆不越界
{
i;
for(i=len;i/2>0&&a[i/2]>x;i/=2)
a[i]=a[i/2];
a[i]=x;
}

template<T>
TDeleteMin(Ta,len)//删除 2叉堆根并通过上移使得新得到序列仍为 2叉堆
{
(len0)
exit(1);
Tmin=a[1];// 2叉堆根
Tlast=a[len--];// 2叉堆最后个元素

c;
i;
for(i=1;i*2<=len;i=c)//把 2叉堆某些元素往前移使得新得到序列仍为 2叉堆
{
c=i*2;//i左儿子
(c!=len&&a[c+1]<a[c])//若i有右儿子且右儿子小于左儿子c指向右儿子[Page]
c;

(last>a[c])//若i小儿子小于 2叉堆最后个元素把其移到i位置
a[i]=a[c];

;
}
a[i]=last;//把 2叉堆最后个元素放到适当空位此时得到序列仍为 2叉堆

min;
}

template<T>
voidHeapSort(Ta,len)
{
T*ca=T[len+1];//复制原到 2叉堆
ca[0]=0;
for(i=0;i<len;i)//把元素依次插入到 2叉堆
Insert(ca,i+1,a[i]);

for(i=0;i<len;i)//依次提取 2叉堆根作为排序后元素
{
a[i]=DeleteMin(ca,len-i);
}

a[len-1]=ca[1];//注意不能忘了最后个元素

deleteca;
}
在数据结构习题和解析(李春葆编著清华大学出版社)中看到个类似算法
它是把原构建成个大顶堆然后把大顶堆第个元素和最后个元素交换；
再把前n-1个元素重新构造成个大顶堆把新大顶堆第个元素和最后个元素交换；
依此类推直到新大顶堆只有个元素这样就得到了个有序 2叉堆
算法如下:
template<T>
voidHeapSort(Ta,len)
{
T*ca=T[len+1];
ca[0]=0;
for(i=0;i<len;i)


ca[i+1]=a[i];

for(i=len/2;i>0;i--)//建立堆[Page]
HeapAdjust(ca,len,i);

for(i=len;i>1;i--)//进行len-1次循环完成堆排序
{
Swap(ca[1],ca[i]);//新大顶堆第个元素和最后个元素交换
HeapAdjust(ca,i-1,1);//筛a[1]元素得到i-1个元素堆
}

for(i=0;i<len;i)
a[i]=ca[i+1];

deleteca;
}

template<T>
voidHeapAdjust(Ta,len,left)//将i和其小儿子交换位置
{
(len0)
exit(1);

Tx=a[left];
i=left;
c=2*i;
while(c<=len)
{
(c<len&&a[c+1]>a[c])//若i有右儿子且右儿子大于左儿子c指向右儿子
c;
(last<a[c])//若i大儿子大于 2叉堆最后个元素把其移到i位置
{
a[i]=a[c];
i=c;
c=2*i;
}

;[Page]
}
a[i]=x;//把原 2叉堆第个元素放到适当空位
}

template<T>
voidSwap(T&a,T&b)
{
Tt=a;
a=b;
b=t;
}

还有种思路方法是每次都要重新调整大顶堆使得父亲比儿子大这样调整较简单但每次都要遍历半元素时间复杂度较大
算法如下:
template<T>
voidHeapSort(Ta,len)
{
T*ca=T[len+1];
ca[0]=0;
for(i=0;i<len;i)
ca[i+1]=a[i];

for(i=len/2;i>0;i--)//把原构建成个大顶堆
HeapAdjust(ca,len,i);
Swap(ca[1],ca[len]);//把大顶堆第个元素和最后个元素交换

for(i=len-1;i>0;i--)
{
for(j=i/2;j>0;j--)//遍历长度为i堆得到新大顶堆
HeapAdjust(ca,i,j);
Swap(ca[1],ca[i]);
}

for(i=0;i<len;i)
a[i]=ca[i+1];



deleteca;
}

template<T>
voidHeapAdjust(Ta,len,i)//将i和其小儿子交换位置
{
c=2*i;

(c<len)
{
T&max=(a[c]>a[c+1])?a[c]:a[c+1];[Page]
(a[i]<max)
Swap(a[i],max);
}

{
(a[i]<a[c])
Swap(a[i],a[c]);
}
}

template<T>
voidSwap(T&a,T&b)
{
Tt=a;
a=b;
b=t;
}

模仿构造大顶堆思路方法我们可以HeapAdjust构造个 2叉堆并提取 2叉堆根到新然后把原 2叉堆最后个元素放到根位置再HeapAdjust构造个新 2叉堆依此类推
算法如下:
template<T>
voidHeapSort(Ta,len)
{
T*ca=T[len+1];
ca[0]=0;
for(i=0;i<len;i)
ca[i+1]=a[i];

for(i=len/2;i>0;i--)//把原构建成个大顶堆
HeapAdjust(ca,len,i);
a[0]=ca[1];
ca[1]=ca[len];//把 2叉堆最后个元素放到根位置

for(i=len-1;i>0;i--)
{
for(j=i/2;j>0;j--)
HeapAdjust(ca,i,j);
a[len-i]=ca[1];
ca[1]=ca[i];//把 2叉堆最后个元素放到根位置[Page]
}

deleteca;
}

template<T>
voidHeapAdjust(Ta,len,i)
{
c=2*i;

(c<len)
{
T&min=(a[c]<a[c+1])?a[c]:a[c+1];
(a[i]>min)
Swap(a[i],min);
}

{
(a[i]>a[c])
Swap(a[i],a[c]);
}
}

template<T>
voidSwap(T&a,T&b)
{
Tt=a;
a=b;
b=t;
}
后面两种思路方法采用是递归容易理解但时间复杂度较高比前两种要慢上很多所以不可能是O(nlogn)估计是O(n^2)但具体我也不会算请高手指教



楼主是做什么？做学问很认真啊看了你BLOG业余？佩服~


我只知道第2个算法





确实是业余啊
我大学读是物理专业,以前对计算机没什么认识,近两年自己有电脑了才逐渐对她感兴趣.

=

偑服!!!!

=

不用n+1个辅助空间只要对下标能够精确确定孩子位置从0开始又何妨？

左孩子=(n+1)*2-1;第个+1是换成元素在堆中编号后个-1是在从堆号换回下标
整理得lchild=n*2+1=(n<<1)+1;

附上我HeapSort代码:

inlineGetLeftChild(parent)
{
((parent<<1)+1);
}

/*percolateA[start]toadjustA[start~end]tomaxheap*/[Page]
/*beforeuseit,makesurethatA[start+1~end]submitheaporder*/
voidPercolateDown(A,start,end)
{
tmp=A[start];
hole=start;
child;

while((child=GetLeftChild(hole))<=end)
{
((child!=end)&&(A[child]<A[child+1]))
{
child;
}
(A[child]>tmp)
{
A[hole]=A[child];
hole=child;/*percalatethehole*/
}

{
;
}
}
A[hole]=tmp;/*fillthehole*/[Page]
;
}

voidHeapSort(A,n)
{
tmp;
i;

/*makeAtoamaxheap*/
for(i=(n>>1)-1;i>=0;--i)
{
PercolateDown(A,i,n-1);
}

/*HeapSort*/
for(i=n-1;i>0;--i)
{
/*DeleteMax*/
tmp=A[0];
A[0]=A[i];


A[i]=tmp;

/*adjustmaxheap*/
PercolateDown(A,0,i-1);
}
}



这里写出为什么建立堆要遍历前半元素

很简单棵完全 2叉树最后个非叶子节点是(n/2)

我们从满 2叉树入手证明:
棵深度为k满 2叉树节点n=2^k-1(等比数列求和)

那么这棵树叶子数leaves=2^(k-1)=(n+1)/2
那么最后个非叶子节点编号就是n-(n+1)/2=(n-1)/2
不用怀疑满 2叉树必须有奇数个节点

再来看完全 2叉树:我们补上x个使的成为满 2叉树
分情况讨论:
1.n为奇数
则x为偶数那么完全 2叉树倒数第 2层有x/2个叶子所以我们要求最后个非叶子节点编号为:(n+x-1)/2-x/2=(n-1)/2
2.n为偶数[Page]
则x为奇数那么完全 2叉树倒数第 2层有(x-1)/2个叶子所以我们要求最后个非叶子节点编号为:(n+x-1)/2-(x-1)/2=n/2

综合1和2得出棵完全 2叉树最后个非叶子节点是(n/2)

所以只要对前半元素从后向前每个做次PercolateDown就能建立个堆



很佩服

=

偶给你提议个算法用混合排序实现快排
3点取中作为枢轴如果偏向边就自动转化为堆排当递归深度大于4转为堆排当基本有序并且分割片段很短时候转化为插入排序其余情况是快排分割这样速度平均比堆排快几倍最坏情况下时间复杂度就是堆排序时间复杂度

延伸阅读

• 2011-9-14-- 堆排序算法,堆排序算法（C#实现）
• 2010-11-24-- 加密算法,谈谈数据加密的处理--提供各种算法处理
• 2011-8-1-- paxos,Paxos算法
• 2011-7-1-- heapsort,堆排序-heapsort
• 2011-3-26-- 堆排序,很好很强大的堆排序
• 2010-12-2-- 负面的惩罚,Google 修改算法以惩罚那些拥有更多负面评论的商户排名
• 2009-9-12-- dllloadex汉化版:Dll  Show  4.7  汉化版注册算法
• 2009-9-12-- dllloadex汉化版:Dll  Show  4.7  汉化版注册算法
• 2009-9-12-- 算法导论:和同学破解了一个邹老大的短信分拆算法！！！！！！！！！！
• 2009-9-12-- 加密算法:破解微软脚本加密算法