Java详细讲解堆排序与时间复杂度的概念（堆排序的时间复杂度?）

目录一、堆排序1、什么是堆排序2、堆排序思想3、代码实现二、时间复杂度分析1、初始化建堆2、排序重建堆3、总结

一、堆排序

1、什么是堆排序

（1）堆排序：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

（2）堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

2、堆排序思想

（1）将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆

（2）将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端

（3）重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序

3、代码实现

import java.util.Arrays;

public class Sort {

//将任意数组进行原地堆排序

public static void heapSort(int[] arr) {

http:// //把数组调整为最大堆，从最后一个非叶子节点开始下沉

for (int i = (arr.length-1-1)/2; i >= 0; i--) {

siftDown(arr,i,arr.length);

}

//将堆顶元素和最后一个元素交换

for (int i = arr.length-1; i > 0 ; i--) {

swap(arr,0,i);

siftDown(arr,0,i);

}

}

//下沉操作

private static void siftDown(int[] arr, int i, int n) {

while ((2 * i)+1 < n){

int j = (2 * i) + 1;

if(j+1arr[j]){

j = j+1;

}

if(arr[i] >= arr[j]){

break;

}else{

swap(arr,i,j);

i = j;

}

}

}

public static void main(String []args){

int []arrOfKpi = {7,6,7,11,5,12,3,0,1};

System.out.println("排序前："+ Arrays.toString(arr));

heapSort(arr);

System.out.println("排序后："+Arrays.toString(arr));

}

}

运行截图：

二、时间复杂度分析

1、初始化建堆

初始化建堆只需要对二叉树的非叶子节点由下至上，由右至左选取非叶子节点来调用adjusthead()函数。那么倒数第二层的最右边的非叶子节点就是最后一个非叶子结点。

假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。高层也是这样逐渐递归。

那么总的时间计算为：s = 2^( i - 1 ) * ( k - i )；其中 i 表示第几层，2^( i - 1) 表示该层上有多少个元素，( k - i) 表示子树上要下调比较的次数。

S = n - log(n) -1，所以时间复杂度为：O(n)

2、排序重建堆

每次重建意味着有一个节点出堆，所以需要将堆的容量减一。adjustheap()函数的时间复杂度k=log(n)，k为堆的层数。所以在每次重建时，随着堆的容量的减小，层数会下降，函数时间复杂度会变化。重建堆一共需要n-1次循环，每次循环的比较次数为log(i)，则相加为：log2+log3+…+log(n-1)+log(n)≈log(n!)。

所以时间复杂度为O(nlogn)

3、总结

初始化建堆的时间复杂度为O(n)，排序重建堆的时间复杂度为nlog(n)，所以总的时间复杂度为O(nlogn)，空间复杂度为O（1）。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。