堆排序法

#include <stdio.h>
void swap(int* a, int* b)
{
int t;
t = *a;
*a = *b;
*b = t;
}
void maxHeapify(int* a, int i, int n)
{
int l, r, m;
do{
r = (i+1) << 1;
l = r - 1;
m = l < n && a[l] > a[i] ? l : i;
m = r < n && a[r] > a[m] ? r : m;
if(i !e799bee5baa6e4b893e5b19e334= m) swap(a+i, a+m), i = m;
else break;
}while(1);
}
void heapSort(int* a, int n){
int i;
for(i = (n-1)/2; i >= 0; --i)
maxHeapify(a, i, n);
for(i = n-1; i > 0; --i)
{
swap(a, a+i);
maxHeapify(a, 0, --n);
}
}
void print(int* a, int* b)
{
while(a < b)
printf("%d ", *a++);
putchar('\n');
}
int main(){
int a[10] = {6,3,1,9,7,4,0,5,8,2};
heapSort(a, 10);
print(a, a+10);
return 0;
}

堆排序法，就是通过堆这种数据结构来实现排序，算法复杂度为O(nlogn)。
堆是一种完全二叉树且所有的父节点均大于（或小于）e68a84e8a2ade79fa5e98193339其子节点。
堆排序就是将所有待排序的元素组成一个堆，然后不断弹出堆顶的元素并调用函数维持堆序，直到所有元素均被弹出后，排序完成。被弹出的元素序列即一个有序数列。

维持堆序的一般做法是这样：

当一个节点被插入时，将该节点放在堆的末尾（这是为了保证堆是完全二叉树）然后将该节点与它的父节点比较，看该节点是否大于（或小于）其父节点，即判断当前的堆是否满足堆序。如果不满足，则将该节点与其父节点交换。再将该节点与其新的父节点做比较，依此类推，直到该节点不再需要与其父节点交换为止。（即满足堆序时停止）

当一个根节点被弹出（即被从堆中删除）时，将堆最尾部的节点移动到头结点的位置，然后将该节点不断与其子节点比较，如果不符合堆序则交换，直到符合堆序为止。

以下是我自己写的一个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=0;i<n;i++)
{
cin>>a;
Insert(a);
}
for(i=0;i<n;i++)
cout<<Pop()<<' ';
system("pause");
return 0;
}
（1）交换类排序法交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类排序方法。冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n–1)/2。但这个工作量不是必需的，一般情况下要小于这个工作量。快速排序法也是一种交换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。其关键是对线性表进行分割，以及对各分割出的子表再进行分割。（2）插入类排序法插入类排序法主要7a686964616fe78988e69d83362有简单插入排序法和希尔排序法。简单插入排序法，是指将无序序列中的各元素依次插入到已经有序的线性表中。在这种排序方法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n–1)/2次比较。希尔排序法对简单插入排序做了较大的改进。它是将整个无序序列分割成若干小的子序列分别进行插入排序。希尔排序的效率与所选取的增量序列有关。在最坏情况下，希尔排序所需要的比较次数为O(n1.5)。（3）选择类排序选择类排序主要有简单选择类排序法和堆排序法。简单选择排序法的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的线性表，在最坏情况下需要比较n(n–1)/2次。堆排序法也属于选择类排序法。具有n个元素的序列（h1, h2, …, hn），当且仅当满足条件： 或 (i=1, 2, …, n/2）时称之为堆。可见，堆顶元素（即第一个元素）必为最大项。堆排序的方法对于规模较小的线性表并不适合，但对于较大规模的线性表来说是很有效的。在最坏情况下，堆排序需要比较的次数为O(nlog2n)。

如果帮助到您，请记得采纳为满意答案哈，谢谢！祝您生活愉快！ vae.la

堆排序就是将所有待排序的元素组成一个堆，然后不断弹出堆顶的元素并调用函数维持堆序，直到所有元素均被弹出后，排序完成。被弹出的元素序列即一个有序数列。  

一般做法是这样：  

当一个节点被插入时，将该节点放在堆的末尾（这是为了保证堆是完全二叉树）然后将该节点与它的父节点比较，看该节点是否大于（或小于）其父节点，即判断当前的堆是否满足堆序。如果不满足，则将该节点与其父节点交换。

再将该节点与其新的父节点做比较，依此类推，直到该节点不再需要与其父节点交换为止。（即满足堆序时停止）  当一个根节点被弹出（即被从堆中删除）时，将堆最尾部的节点移动到头结点的位置，然后将该节点不断与其子节点比较，如果不符合堆序则交换，直到符合堆序为止。

扩展资料：

堆的操作

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似e5a48de588b67a64337完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作： 

最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点 

创建最大堆（Build Max Heap）：将堆中的所有数据重新排序 

堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

参考资料：

百度百科-堆排序