本文共 2033 字，大约阅读时间需要 6 分钟。
核心思想： 使用最大堆，每次从堆顶取出当前最大元素，并与堆末尾元素替换，并且把当前堆大小减少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#include #define MAX 100typedef 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; }
转载地址：http://aximi.baihongyu.com/