算法导论 之 堆排序[C语言]

一、算法实现

堆排序算法的时间复杂度为O（nlgn），其算法实现如下：

void heap_sort(int *array, int max)
{
int idx = 0;

build_max_heap(array, max);

for(idx=max; idx>=2; idx--) {
array[0] = array[1];
array[1] = array[idx];
array[idx] = array[0];

max_heapify(array, 1, idx-1);
}
}

/* 构建大头堆 */

void build_max_heap(int *array, int max)
{
int idx = max/2;

while(idx >= 1) {
max_heapify(array, idx, max);
idx--;
}
}

void max_heapify(int *array, int idx, int max)
{
int left=LEFT(idx), right=RIGHT(idx), largest=-1;

if(left<=max && array[left]>array[idx]) {
largest = left;
} else {
largest = idx;
}

if(right<=max && array[right]>array[largest]) {
largest = right;
}

if(idx != largest) {
array[0] = array[idx];  /* 注：array[0]作为交换空间 */
array[idx] = array[largest];
array[largest] = array[0];

max_heapify(array, largest, max);
}
}

二、函数调用

#define ARRAY_NUM (11)

int main(int argc, char *argv[])
{
int idx = 0;
int array[ARRAY_NUM] = {-1, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

heap_sort(array, ARRAY_NUM-1);

for(idx=1; idx<ARRAY_NUM; idx++) {
fprintf(stdout, "array[%d]=%d\n", idx, array[idx]);
}

return 0;
}