堆是一种完全二叉树且所有的父节点均大于（或小于）其子节点。
堆排序就是将所有待排序的元素组成一个堆，然后不断d出堆顶的元素并调用函数维持堆序，直到所有元素均被d出后，排序完成。被d出的元素序列即一个有序数列。
维持堆序的一般做法是这样：
当一个节点被插入时，将该节点放在堆的末尾（这是为了保证堆是完全二叉树）然后将该节点与它的父节点比较，看该节点是否大于（或小于）其父节点，即判断当前的堆是否满足堆序。如果不满足，则将该节点与其父节点交换。再将该节点与其新的父节点做比较，依此类推，直到该节点不再需要与其父节点交换为止。（即满足堆序时停止）
当一个根节点被d出（即被从堆中删除）时，将堆最尾部的节点移动到头结点的位置，然后将该节点不断与其子节点比较，如果不符合堆序则交换，直到符合堆序为止。
以下是我自己写的一个C++的堆排序的程序，希望对你理解该算法有帮助。
#include<iostream>
using namespace std
int heap[10000],size
void Percup(int s)
{
if(s==1)
return
if(heap[s/2]<heap[s])
{
swap(heap[s/2],heap[s])
Percup(s/2)
}
}
void Percdown(int s)
{
if(s*2+1<=size&&heap[s*2+1]>heap[s])
{
swap(heap[s*2+1],heap[s])
Percdown(s*2+1)
}
if(s*2<=size&&heap[s*2]>heap[s])
{
swap(heap[s*2],heap[s])
Percdown(s*2)
}
}
void Insert(int k)
{
heap[++size]=k
Percup(size)
}
int Pop()
{
int h=heap[1]
heap[1]=heap[size--]
Percdown(1)
return h
}
int main()
{
int a,n,i
cin>>n
for(i=0i<ni++)
{
cin>>a
Insert(a)
}
for(i=0i<ni++)
cout<<Pop()<<' '
system("pause")
return 0
}
我写的是根比叶子大的堆，siftup 是顶堆（就是新来的数据向上，直到它的父亲比自己大，或自己是
堆的根）
程序是对输入数据边读边排的：
program duipai
var
a:array[1..100000]of longint
n:longint
procedure siftup(i:longint)
var
j,b:longint
begin
b:=a[i]
while i>1 do
begin
j:=i shr 1
if a[j]<b then
begin
a[i]:=a[j]
i:=j
end
else break
end
a[i]:=b
end
procedure init
begin
assign(input,'a.in')reset(input)
n:=1
while not seekeof do
begin
read(a[n])
siftup(n)
inc(n)
end
dec(n)
close(input)
end
procedure ansit
var
i:longint
begin
for i:=1 to n do write(a[i],' ')writeln
end
begin
init
ansit
end.
下面的是把最下面的叶子放到堆根上再向下压的程序：
procedure siftdown
var
b,i,j:longint
begin
b:=a[1]i:=1
while i<=n do
begin
j:=i*2
if j>n then break
if (j<n)and(a[j+1]>a[j])then inc(j)
if a[j]>b then
begin
a[i]:=a[j]i:=j
end
else break
end
a[i]:=b
end
如果要改变堆中数据大小顺序，只要改变a[]与b 的比较符号即可
这是快排：
procedure sort(l,r:longint)
var
i,j,t,temp:longint
begin
i:=lj:=rtemp:=a[(i+j)shr 1]
while i<=j do
begin
while a[j]>temp do dec(j)
while a[i]<temp do inc(i)
if i<=j then
begin
t:=a[i]a[i]:=a[j]a[j]:=t
inc(i)dec(j)
end
end
if l<j then sort(l,j)
if i<r then sort(i,r)
end
这是归并排序：
program guibing
var
a,temp:array[1..100000]of longint
n:longint
procedure init
begin
assign(input,'a.in')reset(input)
n:=1
while not eof do
begin read(a[n])inc(n)end
dec(n)
close(input)
end
procedure sort(l,r:longint)
var
i,j,p,mid:longint
begin
if l=r then exit
mid:=(l+r)shr 1
sort(l,mid)
sort(mid+1,r)
i:=lj:=mid+1p:=l
while (i<=mid)or(j<=r)do
begin
if (i<=mid)and(j<=r)then
begin
if a[i]<a[j] then
begin temp[p]:=a[i]inc(i)end
else begin temp[p]:=a[j]inc(j)end
end
else
begin
if i<=mid then begin temp[p]:=a[i]inc(i)end
else begin temp[p]:=a[j]inc(j)end
end
inc(p)
end
for i:=l to r do a[i]:=temp[i]
end
procedure ansit
var
i:longint
begin
for i:=1 to n do write(a[i],' ')writeln
end
begin
init
sort(1,n)
ansit
end.
压堆是为了删掉最上面的根再找到新的最大的根而用的，
如果初始状态不是已经排好的根堆，压堆不会使其成为
一个根堆，而顶堆 *** 作则可生成堆．
我的哪个程序有错？
你需要哪个排序的解释？
快排：
在数组中找一个数，使它左边的数都小于它，右边的数都大于它，并找
到这个数的位置，明显是把整个数组排好序后的位置（记为mid).。再更深一层的
递归，即sort(l,mid-1)sort(mid+1)对这个数左右两边的数再排序，道理一
样，直到处理的数只剩下一个。具体实现你自己F7单步模拟一下吧。
归并：
将数组中的数均分的两部分有序的数归进一个暂时的数组中，从两
部分的起点开始，对当前的两个数比较，哪个小就把哪个送进暂时数组，并
让它在原数组中的下一个数参与下一次比较，直到两部分数全部进入暂时数
组后，将暂时数组的数据覆盖原数组中的数据，使其有序。因为均分的两部
分不一定是有序的，所以要先递归到底，即一个数，在不断回溯时，进行归
并，这时的两部分就是有序的了。
顶堆：
当读入数据时，数据在末尾，这时要不断的向上顶，与它的父亲比较，
直到顶到父亲比自己大或自己在顶点为止，对每一个数据都这样就形成了堆。
压堆：
当最小的数，即堆顶舍弃不用，而需要第二小的数时，就把末尾的数
覆盖到堆顶后向下压，是顶堆的逆过程，即如果叶子比自己小就调换，直到
换不了为止。 *** 作后数据减少一个，但仍是堆。
#include <stdio.h>#include <stdlib.h>
#include <string.h>
int sort_function( const void *a, const void *b)
char list[5][4] = { "cat", "car", "cab", "cap", "can" }
int main(void)
{
int x
qsort((void *)list, 5, sizeof(list[0]), sort_function) // 调用快速排序
for (x = 0x <5x++)
printf("%s\n", list[x])
return 0
}
int sort_function( const void *a, const void *b)
{ //自已要定义一个简单的比较函数就可
return( strcmp((char *)a,(char *)b) )
}
// C++中自身有一个通用的快速 qsort,可以用它 ,自已要定义一个简单的比较函数就可
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）