有了域名之后怎么做自己的网站,seo免费优化网站,wordpress如何轮播,晋中北京网站建设含义
堆排序就是把数组的内容在心中建立为大根堆#xff0c;然后每次循环把根顶和没交换过的根末进行调换#xff0c;再次建立大根堆的过程
建树的几个公式
一个数组有n个元素
最后一个父亲节点是n/2-1;
假如父亲节点在数组的下标为a
那么左孩子节点在数组下标为2*a1,…含义
堆排序就是把数组的内容在心中建立为大根堆然后每次循环把根顶和没交换过的根末进行调换再次建立大根堆的过程
建树的几个公式
一个数组有n个元素
最后一个父亲节点是n/2-1;
假如父亲节点在数组的下标为a
那么左孩子节点在数组下标为2*a1,右孩子节点在数组下标为2*a2
大根堆在心里建树的要点
父亲节点必须大于孩子节点孩子节点大小位置无影响
【注】数组界限问题以及传参问题
核心代码
//其实没有树只不过是我们在心里根据数组层次建树来构建大根堆调整数组的排列顺序
//注意我这里的len是数组的长度注意一下长度和数组下标间的关系
void AdjustDown(int nums[],int pos,int len)
{int dad pos;int son 2*dad1;//左孩子在数组下标while(son len){if(son1len nums[son]nums[son1]){son;//挑选出左右孩子最大的只需把son1变为右孩子下标}if(nums[son]nums[dad])//只能父亲大于孩子{swap(nums[son],nums[dad]);//交换数据dad son;//把当前孩子作为父亲重新循环son 2*dad1;}else{break;}}
}
#includestdio.h
#includetime.h
#includestdlib.h
//数组
int nums[]{3,87,2,93,78,56,61,38,12,40};
void init_rand(int nums[],int len)
{srand(time(NULL));for(int i0;ilen;i){nums[i]rand()%1001;//(1,100)}
}
//交换数据
void swap(int a,intb)
{int tmp a;ab;btmp;
}
void print(int nums[],int len)
{for(int i 0;ilen ;i ){printf(%d ,nums[i]);}printf(\n);
}//其实没有树只不过是我们在心里根据数组层次建树来构建大根堆调整数组的排列顺序
void AdjustDown(int nums[],int pos,int len)
{int dad pos;int son 2*dad1;//左孩子在数组下标while(son len){if(son1len nums[son]nums[son1]){son;//挑选出左右孩子最大的只需把son1变为右孩子下标}if(nums[son]nums[dad])//只能父亲大于孩子{swap(nums[son],nums[dad]);//交换数据dad son;//把当前孩子作为父亲重新循环son 2*dad1;}else{break;}}
}//待排序数组待排序数组的长度
void heap_sort(int nums[],int len)
{int i;//建立大根堆//从最后一个父亲元素开始for(ilen/2-1;i0;--i){//调整没个父亲节点为大根堆//数组父亲节点所在数组的下标数组长度AdjustDown(nums,i,len);}//建立大根堆之后有序的数据是在我们内心中建的树而不是数组因此我们还需要把他修改为数组中swap(nums[0],nums[len-1]);//先交换树根和最后一个节点的数据(我这里的len代表长度)// print(nums,len);//接着再次进入建立大根堆换数据的循环中直到数组有序for(ilen-1;i0;i--){AdjustDown(nums,0,i);//每次从父亲节点开始这里的i代表长度swap(nums[0],nums[i-1]);//每一次交换树根和除去数组末尾已经换过的末尾// print(nums,len);}}int main()
{int len sizeof(nums)/sizeof(nums[0]);init_rand(nums,len);heap_sort(nums,len);print(nums,len);
}
后序补上解析
