我们之前学了堆：
我们知道堆有小堆和大堆之分，根节点不是最小就是最大的，我们可以利用这个特点实现堆排序
思路：
为什么我们要选择堆排序呢
它的效率相比于冒泡排序要高出不少
1.交换函数
2.向上调整
大堆向上调整，找大的往根节点排，找小的往叶子节点排
所以对比孩子节点和父亲节点，如果孩子节点大于父亲节点，则交换两个节点，然后child走到parent，parent走到（child-1）/ 2
3.向下调整
这就是堆的删除思路，根节点是最大的值，根节点和最后一个叶子节点交换，size--，然后继续大堆排序
4.堆排序
4.1建堆
建大堆，从数组第一个值 a[0] 开始插入建堆
4.2选数排序
就是堆的访问，用while循环控制
5.总代码
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> void Swap(int* p1, int* p2); void AdjustUp(int* a, int child); void AdjustDown(int* a, int size, int parent); 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[child] > a[parent]) { Swap(&a[child], &a[parent]); 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[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else break; } } void HeapSort(int* a, int n) { //建堆 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 sz = sizeof(a) / sizeof(a[0]); HeapSort(a, sz); for (int i = 0; i < sz; i++) { printf("%d ", a[i]); } printf("\n"); return 0; }
