堆排序
堆排序
0x00 选择排序
选择排序的思路 将数组分为两部分，已排序部分和未排序部分，每次从为排序部分找到一个最小元素放到有序部分最后，那么怎么找到最小元素呢？可以遍历 这样时间复杂度总为O(n^2),也可以用最小堆
直接用最小堆，一个一个delete出来，由于必然要有个数组来实现堆又要一个数组来保存最后的结果，因此相对于前面的算法而言，内存一定时能处理的数据减少一半。
算法二则是一种聪明的算法，利用堆本身来排序，而不是一个一个delete出来，用最大堆，生成后，把a[0]与a[n-1]交换，这样最大值就到了最后，然后减堆的长度一，再调整，这样仍然是一个最大堆，然后继续重复 一直到最后。整个数组就有序了。
0x01 代码实现
#include <stdio.h>
#define hugenum 100000
void traversal(int*data,int size){
int i;
for(i=0;i<size;i++){
printf("%d\t",data[i]);
}
printf("\n");
}
void select_sort(int*data,int size){
int i,j;
for(i=0;i<size;i++){
int min=i;
for(j=i;j<size;j++){
if(data[j]<data[min]){
min=j;
}
}
int temp=data[i];
data[i]=data[min];
data[min]=temp;
}
}
void rebuild(int*data,int size,int root){
int parent=root;
int child=(parent+1)*2-1;
for(;child<size;){
int maxpos=child;
if(child+1<size&&data[child+1]>data[child]){
maxpos=child+1;
}
if(data[parent]<data[maxpos]){
int temp=data[parent];
data[parent]=data[maxpos];
data[maxpos]=temp;
parent=maxpos;
child=(parent+1)*2-1;
}else{
break;
}
}
}
void makeheap(int*data,int size){
int i;
for(i=(size+1)/2-1;i>=0;i--){
rebuild(data,size,i);
}
}
void heap_sort(int*data,int size){
int i;
for(i=(size)/2-1;i>=0;i--){
rebuild(data,size,i);
}
printf("%d\n",data[0]);
for(i=size-1;i>0;i--){
int temp=data[i];
data[i]=data[0];
data[0]=temp;
rebuild(data,i,0);
}
}
int main(){
int data[]={5,4,3,2,1};
heap_sort(data,5);
traversal(data,5);
return 0;
}
以上代码测试通过
