dw成品网站成品视频教学,装潢设计图片三室效果图,动态照片制作,网站建设包含的内容数据结构 | 堆排序 文章目录 数据结构 | 堆排序建立大堆排序结果以及全部代码 如果没有看过堆的实现的话可以先看前面的一章堆的实现#xff0c;然后再来看这个堆排序#xff0c;都是比较简单的~~ 这里堆排序首先建堆#xff0c;建堆是要建小堆还是大堆呢#xff1f; 在堆排…数据结构 | 堆排序 文章目录 数据结构 | 堆排序建立大堆排序结果以及全部代码 如果没有看过堆的实现的话可以先看前面的一章堆的实现然后再来看这个堆排序都是比较简单的~~ 这里堆排序首先建堆建堆是要建小堆还是大堆呢 在堆排序算法中建立大顶堆的过程是为了确保堆的根节点是整个堆中最大的元素。 当你需要进行升序排序时你希望最大的元素排在序列的最后。堆排序的基本思想是首先将待排序的序列构建成一个大顶堆然后将堆顶元素最大元素与堆的最后一个元素交换接着对剩余的元素重新构建大顶堆然后再次交换堆顶元素与堆的最后一个元素如此往复直到整个序列有序。建立大顶堆的目的是为了每次交换后将最大的元素沉到序列的末尾逐步形成有序的序列。如果你希望升序排序建立大顶堆是符合这一目标的。 建立大堆
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}
void AdjustUp_Big(HPDataType* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}测试一下
int a[] { 4,6,2,1,5,8,2,9 };
int sz sizeof(a) / sizeof(a[0]);
for (int i 1; i sz; i)
{AdjustUp_Big(a, i);
}排序
void AdjustDown_Big(HPDataType* a, int size, int parent)
{int child parent * 2 1;while (child size){if (child 1 size a[child 1] a[child])child;if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}//end是在最后一个元素的下标-1
int end sz - 1;
while (end 0)
{//根和最后一个值进行交换最后一个数不看做堆里面的Swap(a[0], a[end]);AdjustDown_Big(a, end, 0);--end;
}结果以及全部代码
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}
void AdjustUp_Big(HPDataType* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}
void AdjustDown_Big(HPDataType* a, int size, int parent)
{int child parent * 2 1;while (child size){if (child 1 size a[child 1] a[child])child;if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}void HeapSort()
{//建大堆int a[] { 4,6,2,1,5,8,2,9 };int sz sizeof(a) / sizeof(a[0]);/*for (int i 1; i sz; i){AdjustUp_Big(a, i);}*///向下调整建堆这样效率更高上面那个也可以for (int i (sz - 1 - 1)/2; i 0; --i){AdjustDown_Big(a, sz, i);}//打印printf(排序前:);for (int i 0; i sz; i){printf(%d , a[i]);}printf(\n);//排序//end是在最后一个元素的下标-1int end sz - 1;while (end 0){//根和最后一个值进行交换最后一个数不看做堆里面的Swap(a[0], a[end]);AdjustDown_Big(a, end, 0);--end;}//打印printf(排序后:);for (int i 0; i sz; i){printf(%d , a[i]);}
}
