合肥营销型网站建设,wordpress 简码插件,东莞华商网络科技有限公司,禹州网站建设堆排序 堆排序是一种基于二叉堆数据结构的排序算法#xff0c;它的基本概念包括#xff1a;
建立堆#xff1a;将待排序的列表构建成一个二叉堆#xff0c;即满足堆的性质的完全二叉树#xff0c;可以是最大堆或最小堆。最大堆要求父节点的值大于等于其子节点的值#x…堆排序 堆排序是一种基于二叉堆数据结构的排序算法它的基本概念包括
建立堆将待排序的列表构建成一个二叉堆即满足堆的性质的完全二叉树可以是最大堆或最小堆。最大堆要求父节点的值大于等于其子节点的值最小堆则要求父节点的值小于等于其子节点的值。堆调整将堆顶元素根节点与最后一个元素交换然后对剩余的n-1个元素重新调整成堆此时堆顶元素为最大或最小元素。重复堆调整重复进行堆调整操作每次将堆中最大或最小的元素放到列表的末尾并将剩余元素重新调整成堆。完成排序当所有元素都已经被移出堆列表就变成了一个有序序列。
堆排序的时间复杂度为O(nlogn)它是一种不稳定的排序算法。
完全二叉树是一种特殊的二叉树它的基本概念包括
完全二叉树是指除了最底层外其他层的节点都是满的并且最底层的节点都靠左排列。换句话说如果用层次遍历的顺序来访问完全二叉树的节点那么节点的顺序是从左到右依次排列的不会出现空缺。如果将完全二叉树的节点按从上到下、从左到右的顺序编号那么对于任意一个节点i如果其父节点存在那么其父节点的编号为i/2如果其左子节点存在那么左子节点的编号为2i如果其右子节点存在那么右子节点的编号为2i1。完全二叉树通常使用数组来进行存储而不是链式存储。这是因为完全二叉树的特性使得节点之间的关系可以通过数组的下标计算得出节省了存储空间。
完全二叉树常常用于堆数据结构的实现因为其特殊的性质使得堆操作更加高效。
堆排序cpp代码截图
堆排序cpp代码
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
#include stdlib.h
#include math.h
#include iostream
#include string.h
#include time.h
#include sys/timeb.h
#define MAX 10
using namespace std;// 打印函数
void PrintArray(int arr[], int length) {for (int i 0; i length; i) {cout arr[i] ;}cout endl;}
// 交换函数
void MySwap(int arr[], int a, int b) {int temp arr[a];arr[a] arr[b];arr[b] temp;}/*param myArr 待调整的数组param index 待调整的节点下标param len 数组的长度
*/
void HeapAdjust(int myArr[], int index, int len) {int max index; // 保存当前节点的下标int lchild index * 2 1;int rchild index * 2 2;if (lchild len myArr[lchild] myArr[max]) {max lchild;}if (rchild len myArr[rchild] myArr[max]) {max rchild;}if (max ! index) {//交换两个节点MySwap(myArr, max, index);HeapAdjust(myArr, max, len);}}
// 堆排序的代码
void HeapSort(int myArr[], int len) {// 初始化堆大顶堆从小到大for (int i len / 2 - 1; i 0; i--) {HeapAdjust(myArr, i, len);}// 交换堆顶的元素和最后的元素for (int i len - 1; i 0; i--) {MySwap(myArr, 0, i);HeapAdjust(myArr, 0, i);}
}
int main()
{int myArr[] {4,2,8,0,5,7,1,3,9};int len sizeof(myArr) / sizeof(myArr[0]);PrintArray(myArr, len);// 堆排序HeapSort(myArr, len);PrintArray(myArr, len);
}堆排序运行结果展示
