c语言如何实现数组排序（数组排序之堆排序）

采用堆排序的方法去排序一个数组{47, 35, 26, 20, 18, 7, 13, 10}

数组对应堆的图例，根节点大于左右孩子节点

分析：

1. 组建堆，第i个节点和其左右孩子分别对应第2*i 1和2*i 2下标的数据

2. 如何确定堆有几层？如下

3. 数组的最后一个值得下标为n其父节点为i，所以存在关系n = 2*i 1 => i = (n-1)/2

4. 即第0~i个节点是有子节点，i 1~n个节点是叶子节点

5. 首次建堆处理，把树处理成根节点大于或等于其左右孩子的树

6. 首次建堆后的数据是大根堆，但是此时从上往下，从左往右并不是有序的

7. 然而，首次建堆不是有序的，但是此时堆顶元素肯定是最大的

8. 因此把堆顶元素和数组最后一个元素交换位置，然后剔除掉最后一个元素，重新建堆

9. 为此时，除了第一个元素，其他元素都是符合大根堆关系的，因此，从0开始建堆（不同于一开始的，以每一个小节点建堆，再逐步组装起来）

10. 最后的堆顶元素是最大的，重复7、8步骤，直到全部元素处理完毕。

#include<iostream> using namespace std; class Heap { private: int arr[10] = {47, 35, 26, 20, 18, 7, 13, 10, 8, 6}; public: void show(); void sort(int n); void sortHeap(int k, int n); // 在当前节点中排序 }; void Heap::show() { for (int i = 0; i < 10; i ) { cout<<this->arr[i]<<" "; } cout<<endl; } // n 表示数组长度，k表示该根节点的下标 void Heap::sortHeap(int k, int n) { int i, j, temp; i = k; j = 2 * i 1; // 操作第k层和其孩子比较 while(j < n) { // 在数组边界内, 比较左右孩子，较大的孩子与根节点比较 if (j < n-1 && this->arr[j] < arr[j 1]) j ; if (this->arr[i] > this->arr[j]) { break; } else { temp = this->arr[i]; this->arr[i] = this->arr[j]; this->arr[j] = temp; this->show(); // 交换后，后面可能存在大于改根节点的值，所以交换后的节点作为根节点，继续比较，直到条件不成立 i = j; j = 2*i 1; } } } void Heap::sort(int n) { int i, temp; // 从后往前遍历有根节点，最后一个根节点的下标n=2*i 1 => i = (n-1) / 2得到根节点 for (i = (n-1)/2; i >= 0; i--) { this->sortHeap(i, n); this->show(); } cout<<"---"<<endl; // 将堆顶的数值和最后一个未交换过的下标的值交换，得到的下标n-i是目前未处理的最大的数值 for (i = 1; i <= n-1; i ) { cout<<"堆顶"<<this->arr[i]<<endl; temp = this->arr[0]; this->arr[0] = this->arr[n - i]; this->arr[n-i] = temp; // 重新建队，n-i个节点下标后已经是处理过的值，不需要在堆中处理 this->sortHeap(0, n-i); } this->show(); } int main() { Heap heap; // heap.show(); heap.sort(10); heap.show(); return 0; }