堆排序
堆排序分为建堆,调整堆两个步骤。
关键是分清数组大小和堆大小,因为数组的最后几个元素已经是排好序,相当于从堆中移除了。
#include <iostream>
using namespace std;
void HeapAdjust(int *a, int i, int size)
{
int lchild = 2*i;
int rchild = 2*i + 1;
int max = i;
if(i <=size/2)
{
if(lchild <=size && a[lchild] > a[max] )
{
max = lchild;
}
if(rchild <=size && a[rchild] > a[max])
{
max = rchild;
}
if(max != i)
{
swap(a[i], a[max]);
HeapAdjust(a, max, size);
}
}
}
void BuildHeap(int *a, int size)
{
int i;
for(i = size/2; i >= 1; i--)
{
HeapAdjust(a, i, size);
}
}
void HeapSort(int *a, int size)
{
int i;
BuildHeap(a, size);
for(i=size;i>=1;i--)
{
swap(a[1], a[i]);
HeapAdjust(a, 1, i-1);
}
}
int main(int argc, char* argv[])
{
int i;
int a[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
HeapSort(a, 10);
for(i=1;i<=10;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。