学校文化建设网站,出口俄罗斯的外贸公司,网站建设公司市场,seo权威入门教程目录 1.思路1.1大堆的建立方法1.2排序的方法 2.代码实现以及测试代码 1.思路
如何将一个堆进行排序#xff0c;并变成升序#xff1f;首先#xff0c;如果要完成升序#xff0c;那我们可以建立一个大堆#xff0c;因为大堆可以选出一个最大的值放在堆的最上面#xff0c… 目录 1.思路1.1大堆的建立方法1.2排序的方法 2.代码实现以及测试代码 1.思路
如何将一个堆进行排序并变成升序首先如果要完成升序那我们可以建立一个大堆因为大堆可以选出一个最大的值放在堆的最上面我们就可以根据每次选出一个最大值来进行排序的做法.
1.1大堆的建立方法
值得一说的是如果给定一个数组让进行建堆排序操作的话建立大堆可以有两种不同的过程两种过程对应了不同的时间复杂度 首先第一种向上调整法
for (int i 1; i n; i)
{AdjustUp(a, i);
}如图所示时间复杂度为ON*logN 另一种方法向下调整法: 与向上调整法不同的是向下调整法开始的第一个节点是最后一个非叶子节点 for (int i (n - 1 - 1) / 2; i 0; i–) { AdjustDown(a, n, i); } 如图所示时间复杂度为:ON
1.2排序的方法
利用大堆的特点每次选出一个最大值并与最后一个值进行交换换到最后得到的数组就为排序好的数组.
int end n - 1;
while (end 0)
{Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;
}
2.代码实现以及测试代码
实现代码:
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void AdjustUp(int* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[parent] a[child]){Swap(a[parent], a[child]);child parent;parent (child - 1) / 2;}else{break;}}}
void AdjustDown(int* 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[parent] a[child]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}}void HeapSort(int* a, int n)
{for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}//for (int i 1; i n; i)//{// AdjustUp(a, i);//}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);end--;}}
测试代码: int main()
{ int a[] { 4,6,2,1,5,8,2,9 };int size sizeof(a) / sizeof(int);HeapSort(a, size);for (int i 0; i size; i){printf(%d , a[i]);}return 0;
}运行截图:
结尾今天的分享到此结束喜欢的朋友如果感觉有帮助可以点赞三连支持咱们共同进步!
