堆排序
前面我们已经实现了堆的实现，其中堆的实现中最重要的算法就是向上调整和向下调整了。接下来的堆排序也同样的跟这两种算法息息相关。所以向上调整和向下调整这两种算法一定要好好掌握。
在学习堆排序之前我们先来思考一个问题，既然是堆排序，那么我们在对数据进行排序的时候是否真的需要一个堆呢？是否真的需要先提前把这个堆的数据结构实现完成之后才能实现堆排序这个算法呢？
如果真是这样的话那岂不是太麻烦了。所以我们不需要提前实现好堆，我们可以处理数组中的元素使这个数组中的元素变成一个堆。大家不要忘记了，堆是在完全二叉树的基础上增加了一个限制条件，这个限制条件就是堆的某个结点总是不大于或者不小于其父结点的值；另外这个堆底层就是用数组来实现的。
我们在实现堆排序的时候可以把这个数组想象成一个完全二叉树，然后通过一定的算法实现把这个完全二叉树搞成一个堆。我们通常把这个过程叫做建堆。
好了，实现堆排序的第一步就是把数组中的数据搞成一个堆，即我们必须先实现建堆的算法。而建堆有两种方法来实现，一种是向上调整法，另一种就是向下调整法。
建堆
向上调整法建堆
通过利用我们刚刚实现堆的向上调整的算法来建堆（不要把这个算法想象的那么高深莫测，其实就是我们对这个数组进行一定的算法实现使这个数组中的元素变成堆的数据结构），最终结果是建立一个大根堆。
我们直接看最关键的向上调整法的代码：
void AdjustUp(int* a, int child) { //父亲就是(孩子-1)/2 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; } } }
此时，我们就会得到一个数组，这个数组中的元素就是一个大根堆的结构。
这个过程就是模拟插入建堆（操控的数组的数据，而不是堆中的数据）。
举个例子吧：
这个数组经过向上调整法之后就变成了这样：
如果想要得到一个小根堆的话，只需要把向上调整法中a[child] > a[parent]的>改为<就可以了，即a[child] < a[parent]。程序运行之后就是：
所以这里得到的就是一个小根堆。
向下调整法建堆
//向下调整建堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown2(a, n, i); }
利用堆删除的思想来进行排序
刚刚通过向上调整法已经建立了大堆或者小堆，接下来就开始进行排序了。对于排序的话，无非就是升序和降序。
结论就是：升序用大堆，降序就用小堆。
我们先来看升序的过程（总共有两个步骤）：
第一步就是先利用向上调整建立一个大堆，第二步就是利用堆删除的思想来排序，最终就会得到一个升序的数组。
这里我简单说一下第二个步骤（利用向下调整来进行实现）：我们通过第一步建立了一个大堆，接下来开始第二步：让堆顶和堆尾进行交换，然后对此时的堆顶进行向下调整，接着交换堆顶和堆中倒数第二个数据，再次对此时堆顶的数据进行向下调整；重复此过程。最终就可以得到一个升序的数组。
下面是升序过程中最核心的代码：
void AdjustUp(int* a, int child) { //父亲就是(孩子-1)/2 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 AdjustDown2(int* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child] < a[child + 1]) { 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[end], &a[0]); //AdjustDown1(a, end, 0); AdjustDown2(a, end, 0); end--; } }
上图就是整个升序的过程：先利用向上调整来建立一个大堆，然后利用向下调整进行升序排序（第二个过程其实就是一个堆删除的思想）。
升序代码
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<assert.h> #include<stdlib.h> void swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void AdjustUp(int* a, int child) { //父亲就是(孩子-1)/2 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 AdjustDown2(int* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child] < a[child + 1]) { 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[end], &a[0]); //AdjustDown1(a, end, 0); AdjustDown2(a, end, 0); end--; } } int main() { int a[10] = { 8,5,2,1,4,7,9,6,3,10 }; HeapSort(a, 10); for (int i = 0; i < 10; i++) { printf("%d ", a[i]); } return 0; }
降序代码
其实降序和升序的思路可以说基本上就是一模一样的。
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<assert.h> #include<stdlib.h> void swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void AdjustUp(int* a, int child) { //父亲就是(孩子-1)/2 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 AdjustDown1(int* a, int n, int parent) { int child = parent * 2 + 2; while (child < n) { if (child < n && a[child - 1] < a[child]) { child--; } if (a[child] < a[parent]) { swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 2; } else { break; } } } //向下调整，基础为大堆 void AdjustDown2(int* a, int n, int parent) { int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child] < a[child + 1]) { 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); } 向下调整建堆 //for (int i = (n - 1 - 1) / 2; i >= 0; i--) //{ // AdjustDown1(a, n, i); //} int end = n - 1; while (end > 0) { swap(&a[end], &a[0]); AdjustDown1(a, end, 0); //AdjustDown2(a, end, 0); end--; } } int main() { int a[10] = { 8,5,2,1,4,7,9,6,3,10 }; HeapSort(a, 10); for (int i = 0; i < 10; i++) { printf("%d ", a[i]); } return 0; }
好了，以上就是这篇文章的全部内容了，说实话，不简单，这需要我们不断的理解才可以把着块的内容吃透。
诸位一起加油吧！！！就到这里，再见啦，各位
