1.思路
如何将一个堆进行排序，并变成升序？首先，如果要完成升序，那我们可以建立一个大堆，因为大堆可以选出一个最大的值放在堆的最上面，我们就可以根据每次选出一个最大值来进行排序的做法.
1.1大堆的建立方法
值得一说的是，如果给定一个数组，让进行建堆排序操作的话，建立大堆可以有两种不同的过程，两种过程对应了不同的时间复杂度
首先第一种：向上调整法
for (int i = 1; i < n; i++) { AdjustUp(a, i); }
如图所示，时间复杂度为：
O（N*logN）
另一种方法：向下调整法:
与向上调整法不同的是，向下调整法开始的第一个节点是最后一个非叶子节点
for (int i = (n - 1 - 1) / 2; i >= 0; i–) { AdjustDown(a, n, i); }
如图所示，时间复杂度为:
O（N），
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; }
运行截图:
结尾：今天的分享到此结束，喜欢的朋友如果感觉有帮助可以点赞三连支持，咱们共同进步!
