构建堆的时间复杂度为O(n),而第I次调整堆的时间复杂度为O(logi),因此，无论什么情况下时间复杂度都为O(nlogn)。
算法思想：
首先，对数组从n/2处开始进行创建堆。大顶堆就是顶点总是大于它的子节点，而小顶堆就是定点总是小于它的子节点。
因此，构建时，对节点与他的孩子进行比较，如果创建的是大顶堆，那么就把最大的孩子跟自己进行比较，比自己大，就进行替换。依次类推。
最后把最顶点的与最后一个元素进行替换，在进行堆的调整，此时的调整，相当于调整最顶点的元素。
主要代码：
void heapSort(int *arr,int length){ int i; for(i=length/2; i>0; i--){ sort(arr,i,length); } for(i=length; i>0; i--){ int k = arr[0]; arr[0] = arr[i-1]; arr[i-1] = k; sort(arr,1,i-1); } } void sort(int *arr,int s,int length){ int temp,i; temp = arr[s-1]; for(i=2*s; i<=length; i*=2 ){ if(i<length && arr[i-1] < arr[i]) i++; if(temp >= arr[i-1]) break; arr[s-1] = arr[i-1]; s = i; } arr[s-1] = temp; }
全部代码：
#include <stdio.h> #include <stdlib.h> #include <time.h> int arrtest1[10] = {3,4,7,8,0,9,1,2,6,5}; int arrtest2[10] = {0,1,2,3,4,5,6,7,8,9}; int arrtest3[10] = {9,8,7,6,5,4,3,2,1,0}; void copy(int *from,int *arr,int length); void print(int *arr,int length); void heapSort(int *arr,int length); void sort(int *arr,int s,int length); int main(){ clock_t start,end; int Arr[10]; int i; copy(arrtest1,Arr,10); print(Arr,10); heapSort(Arr,10); print(Arr,10); start = clock(); for(i=0;i<100000;i++){ copy(arrtest1,Arr,10); //print(Arr,10); heapSort(Arr,10); //print(Arr,10); } end = clock(); printf("first test:%d\n",end-start); start = clock(); for(i=0;i<100000;i++){ copy(arrtest2,Arr,10); //print(Arr,10); heapSort(Arr,10); //print(Arr,10); } end = clock(); printf("first test:%d\n",end-start); start = clock(); for(i=0;i<100000;i++){ copy(arrtest3,Arr,10); //print(Arr,10); heapSort(Arr,10); //print(Arr,10); } end = clock(); printf("first test:%d\n",end-start); getchar(); return 0; } void heapSort(int *arr,int length){ int i; for(i=length/2; i>0; i--){ sort(arr,i,length); } for(i=length; i>0; i--){ int k = arr[0]; arr[0] = arr[i-1]; arr[i-1] = k; sort(arr,1,i-1); } } void sort(int *arr,int s,int length){ int temp,i; temp = arr[s-1]; for(i=2*s; i<=length; i*=2 ){ if(i<length && arr[i-1] < arr[i]) i++; if(temp >= arr[i-1]) break; arr[s-1] = arr[i-1]; s = i; } arr[s-1] = temp; } void copy(int *from,int *arr,int length){ int i; for(i=0;i<length;i++){ arr[i] = from[i]; } } void print(int *arr,int length){ int i; for(i=0;i<length;i++){ printf("%d ",arr[i]); } printf("\n"); }
运行示例：
本文转自博客园xingoo的博客，原文链接：堆排序，如需转载请自行联系原博主。
