堆排序算法时间复杂度是什么,java各种排序的时间复杂度
00-1010 1.堆排序1。什么是堆排序2。堆排序思路3。代码实现2。时间复杂度分析1。初始化堆构建2。排序和重建堆3。总结。
目录
00-1010 (1) Heapsort:堆排序是指利用堆的数据结构设计的一种排序算法。Heap是一种类似于完全二叉树的结构，同时满足heap的性质：即子节点的键值或索引总是小于(或大于)其父节点。
(2)堆是一个完全二叉树，具有以下性质：每个节点的值大于或等于其左右子节点的值，称为大顶堆；或者每个节点的值小于或等于其左右子节点的值，称为小顶堆。
00-1010 (1)把不需要的序列堆成一个堆，按照需求的升序和降序选择大顶堆或者小顶堆。
(2)用end元素交换top元素，将最大的元素下沉到数组末尾。
(3)重新调整结构以满足堆定义，然后继续交换顶层元素和当前最后一个元素，重复执行调整和交换步骤，直到整个序列有序。
一、堆排序
导入Java . util . arrays；PublicSort {//Sort任意数组就地堆public static void heap(int[]arr){//从最后一个非叶节点开始，将数组调整到最大堆和sink for(int I=(arr . length-1-1)/2；I=0；i - ) { siftDown(arr，I，arr . length)；}//将堆的顶部元素和最后一个元素交换为(int I=arr . length-1；I 0；i - ) { swap(arr，0，I)；siftDown(arr，0，I)；}}//sinking操作私有静态void sift down (int [] arr，int i，int n){ while((2 * I)1n){ int j=(2 * I)1；if(j 1n arr[j 1]arr[j]){ j=j 1；} if(arr[I]=arr[j]){ break；}else{ swap(arr，I，j)；I=j；} } }公共静态void main(String[]args){ int[]arr={ 7，6，7，11，5，12，3，0，1 }；System.out.println(排序前： arrays . tostring(arr))；堆排序(arr)；System.out.println(排序后： arrays . tostring(arr))；}}跑步截图：
1、什么是堆排序
00-1010初始堆构建只需要从下到上从右到左选择二叉树的非叶节点就可以调用adjusthead()函数。那么倒数第二层最右边的非叶节点就是最后一个非叶节点。
假设高度为k，从倒数第二层右侧的节点开始，这一层的所有节点都要进行子节点比较，然后交换；在倒数第二层，将选择其子节点进行比较和交换。如果没有交换，就没有必要再表演了。高层也是如此。
那么总时间计算为：s=2^(I-1)*(k-I)；其中I表示哪一层，2^(i-1)表示这一层有多少个元素，而(k-i)表示子树上的比较降级的次数。
S=n-log(n) -1，所以时间复杂度为：O(n)
00-1010每次重建都意味着一个节点不在堆中，所以堆的容量需要减少一个。adjustheap()函数的时间复杂度k=log(n)，其中k是堆层数。所以在每次重构中，随着堆容量的减少，层数会减少，函数的时间复杂度也会发生变化。重建堆总共需要n-1个周期，每个周期的比较次数为log(i)，所以总和为：log2 log3 … log(n-1) log(n)log(n！)。
因此，时间复杂度为O(nlogn)
00-1010初始堆建立的时间复杂度为O(n)，排序重建堆的时间复杂度为nlog(n)，所以总时间复杂度为O(nlogn)，空间复杂度为O(1)。
这就是这篇关于Java的文章，详细解释了堆排序和时间复杂度的概念。关于Java堆排序和时间复杂度的更多信息，请搜索以前关于流行IT的文章或者继续浏览下面的相关文章。我希望你以后能更多地支持流行音乐！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。