核心思想： 使用最大堆，每次从堆顶取出当前最大元素，并与堆末尾元素替换，并且把当前堆大小减少1，进行n-1次后 排序完成。
时间复杂度: o(NlogN)
核心代码：
//如果数组从0开始则取不到size 下面的 child ！= size-1 (关键) 若写成child != size 则越界
//如果数组从1开始存数据 则要取到size 下面相应写成child != size
void adjust_heap(Heap *h, int i, int size)
{
int child, parent;
int tmp = h->data[i]; //整个过程就是下滤操作 不断调整堆
for(parent = i; parent*2 + 1 < size; parent = child){
child = parent*2+1;
if(child != size-1 && h->data[child] < h->data[child+1])
child++;
if(h->data[child] > tmp){
h->data[parent] = h->data[child];
}
else
break;
}
h->data[parent] = tmp;
}
void heap_sort(Heap *h, int n)
{
int i;
for(i = n/2-1; i >= 0; i--){ //i的初始值与数组存元素的开始索引有关 （调整为最大堆的过程）
adjust_heap(h, i, n);
}
for(i = n-1; i > 0; i--){ //最后剩下的一个是最小的元素
swap(&h->data[0], &h->data[i]);
adjust_heap(h, 0, i);
}
printf("排序后:\n");
for(i = 0; i < h->size; i++ ){
printf("%d ",h->data[i]);
}
}
完整实现：
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
typedef struct HeapNode{
int size;
int data[MAX];
}Heap;
void init_heap(Heap *h)
{
h->size = 0;
}
void build_heap(Heap *h)
{
int n;
scanf("%d",&n);
h->size = n;
int i;
printf("排序前:\n");
for(i = 0; i < n; i++ ){
scanf("%d",&h->data[i]);
}
}
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void adjust_heap(Heap *h, int i, int size)
{
int child, parent;
int tmp = h->data[i];
for(parent = i; parent*2 + 1 < size; parent = child){
child = parent*2+1;
if(child != size-1 && h->data[child] < h->data[child+1])
child++;
if(h->data[child] > tmp){
h->data[parent] = h->data[child];
}
else
break;
}
h->data[parent] = tmp;
}
void heap_sort(Heap *h, int n)
{
int i;
for(i = n/2-1; i >= 0; i--){ //i的初始值与数组存元素的开始索引有关
adjust_heap(h, i, n);
}
for(i = n-1; i > 0; i--){ //最后剩下的一个是最小的元素
swap(&h->data[0], &h->data[i]);
adjust_heap(h, 0, i);
}
printf("排序后:\n");
for(i = 0; i < h->size; i++ ){
printf("%d ",h->data[i]);
}
}
int main()
{
int i;
Heap h;
init_heap(&h);
build_heap(&h);
heap_sort(&h,h.size);
return 0;
}
