二叉树之推排序（升序）

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;
}

运行截图:

结尾：今天的分享到此结束，喜欢的朋友如果感觉有帮助可以点赞三连支持，咱们共同进步!