作者:mobiledu2502875545 | 来源:互联网 | 2023-06-14 12:12
数组排序之堆排序,c++实现-数组排序之堆排序,c++实现问题描述采用堆排序的方法去排序一个数组{47,35,26,20,18,7,13,10}数组对应堆的图例,根节点大于左右孩子
数组排序之堆排序,c++实现
问题描述
采用堆排序的方法去排序一个数组{47, 35, 26, 20, 18, 7, 13, 10}
数组对应堆的图例,根节点大于左右孩子节点
分析:
- 组建堆,第i个节点和其左右孩子分别对应第2i + 1和2i + 2下标的数据
- 如何确定堆有几层?如下
- 数组的最后一个值的下标为n其父节点为i,所以存在关系n = 2*i+1 => i = (n-1)/2
- 即第0~i个节点是有子节点,i+1~n个节点是叶子节点
- 首次建堆处理,把树处理层,根节点大于或等于其左右孩子的树
- 首次建堆后的数据是大根堆,但是此时从上往下,从左往右并不是有序的
- 然首次建堆不是有序的,但是此时堆顶元素肯定是最大的
- 因此把堆顶元素和数组最后一个元素交换位置,然后剔除掉最后一个元素,重新建堆
- 为此时,除了第一个元素,其他元素都是符合大根堆关系的,因此,从0开始建堆(不同于一开始的,以每一个小节点建堆,再逐步组装起来)
最后的堆顶元素是最大的,重复7、8步骤,直到全部元素处理完毕。
算法实现
#include
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<arr[i]<<" ";
}
cout<arr[j] 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<<"---"<arr[i]<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;
}
结果如下