当前位置：首页 > news >正文

折800网站模板腾讯会议开始收费

news 2026/4/7 14:47:02

折800网站模板,腾讯会议开始收费,工业和信息化部关于开展加强网站备案管理专项行动的通知,福建网站开发本期讲解堆排序的实现 —————————————————————— 1. 堆排序堆排序即利用堆的思想来进行排序，总共分为两个步骤： 1. 建堆 • 升序：建大堆 • 降序：建小堆 2. 利用堆删除思想来进行排序. 建堆和堆删…

本期讲解堆排序的实现

——————————————————————

1. 堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆
• 升序：建大堆
• 降序：建小堆
2. 利用堆删除思想来进行排序.

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

PS: 向下调整的代码实现已在上一篇博客最后（Heap.c）分享

堆排序的两种实现

在此，我们提倡第二种堆排序的方法

1.


int a[]={2,5,7,4,1,6,9,8,3};void HeapSort(int* a,int n)
{Heap heap;HeapInitArray(&heap, a, n);//建立了小堆//排序int i = 0;while (!HeapEmpty(&heap)){a[i] = HeapTop(&heap);printf("%d\n",a[i]);i++;//为了打印HeapPop(&heap);}HeapDestroy(&heap);
}

缺点：
1.空间复杂度为O（N）
2.需要去写堆的数据结构（子函数）太麻烦。

2.

//找降序，建小堆
void HeapSort(HeapDataType* a ,int n)
{//1.原数组建小堆，时间复杂度O（N）for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a,n,i);//参数：目的地，个数，开始调整的位置（parent）}//2.交换，继续使用向下调整, 时间复杂度O(N*logN)int end = n - 1;while (end > 0){Swap(&a[0],&a[end]);AdjustDown(a,end,0);--end;}
}

堆排序的时间复杂度为o(N*logN)