堆排序
构建堆的时间复杂度为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");
}运行示例：
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2014-04-14 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
