佛山网站制作哪家便宜,seo优化效果,做h5免费软件有哪些,wordpress主题圆角堆排序的时间复杂度是O#xff08;N*logN#xff09;#xff0c;优于选择排序O#xff08;N^2#xff09;
一、堆 1.堆的概念#xff1a;堆一般指的是二叉堆#xff0c;顾名思义#xff0c;二叉堆是完全二叉树或者近似完全二
2.堆的性质#xff1a;①完全二叉树 ②每…堆排序的时间复杂度是ON*logN优于选择排序ON^2
一、堆 1.堆的概念堆一般指的是二叉堆顾名思义二叉堆是完全二叉树或者近似完全二
2.堆的性质①完全二叉树 ②每个节点的值都大于或等于其子节点的值为最大堆反之为最小堆。
3.堆的存储结构是数组逻辑结构是二叉树 二、 堆排序包括建堆和排序
1.建堆的实现原理
用到向下调整算法比较两个孩子的大小选出大的孩子与父亲比较如果孩子大于父亲交换。然后把parentchildchildparent*21向下调整算法一共会调整h-1次因此时间复杂度是OlogN
从最后一个非叶子的节点开始用向下调整算法实现建大堆。建小堆就是 符号的改变
2.向下调整算法的过程 void swap(int* a, int* b)//实现交换的函数
{int tmp *a;*a *b;*b tmp;
}
//前提下面都是大堆
void AdjustDown(int* a, int n,int root)//向下调整算法
{int parent root;int child parent * 2 1;//默认是左孩子逻辑结构中二叉树的一个规律左孩子父亲*21while (child n){if (child1n a[child] a[child1])//排大堆如果右孩子更大就让child是右孩子{child 1;}if (a[child] a[parent])//排大堆如果孩子大于父亲交换并且依次向下调整{swap(a[parent], a[child]);parent child;child parent * 2 1;}else//已经是大堆了退出while循环{break;}} 3.建堆
//建堆从最后一个非叶子节点开始调整就可以达到下面都是大堆
for (int i (n - 1 - 1) / 2; i 0; i--)//n-1是最后一个数组下标求父亲(下标-1)/2
{AdjustDown(arr, n, i);
}
4.建堆的时间复杂度是ON--粗略的了解原理记住结论就行 5.排序用大堆
用小堆的坏处交换之后踢出第一个数会导致堆的错位要重新建堆时间复杂度ON^2
排序的原理
把第一个最大的数与最后一个数交换然后把最后一个数踢出堆继续向下调整算法再交换次大的数。
int end n - 1;
while (end 0)
{swap(arr[0], arr[end]);AdjustDown(arr, end, 0);//把交换之后的根向下调整调整h-1次又变成大堆再交换可以得到次小的数end--;
} 堆排序的所有代码
#includestdio.h
void swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}
//前提下面都是大小堆
void AdjustDown(int* a, int n,int root)
{int parent root;int child parent * 2 1;//默认是左孩子while (child n){if (child1n a[child] a[child1])//排大堆{child 1;}if (a[child] a[parent])//排大堆{swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}
void HeapSort(int* arr, int n)
{for (int i (n - 1 - 1) / 2; i 0; i--)//n-1是最后一个数组下标求父亲(下标-1)/2{AdjustDown(arr, n, i);}int end n - 1;while (end 0){swap(arr[0], arr[end]);AdjustDown(arr, end, 0);//把交换之后的根向下调整调整h-1次又变成大堆再交换可以得到次小的数end--;}
}
int main()
{int arr[] { 10,1,5,3,6,8,7,4,9};int n sizeof(arr) / sizeof(arr[0]);HeapSort(arr, n);for (int i 0; i n; i){printf(%d , arr[i]);}return 0;
}
