堆排序算法图VS JAVA代码实现

初步知识

堆排序

堆排序是利用堆的数据结构设计的排序算法。堆排序是一种选择排序，其最坏、最好、平均时间复杂度均为O(nlogn)，也是不稳定排序。首先我们简单了解一下堆结构。

堆

堆是一棵完全二叉树，具有以下性质：每个节点的值都大于或等于其左右子节点的值，称为大顶堆；或者每个节点的值小于或等于其左右子节点的值，称为小顶点堆。如下图：

同时我们对堆中的节点逐层进行编号。将此逻辑结构映射到数组看起来像这样

数组在逻辑上是一个堆结构。我们用简单的公式来描述堆的定义为：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

Small顶堆： arr [i] temp){ //如果子节点大于父节点，则将子节点值赋给父节点（无需交换）

arr [i] = arr[ k];

i = k;

}else{

暂停;

}

arr[i] = temp;//改变临时值放到最后位置

}

/**

* 切换元素 ♶r* @param❝ a

* @param b

*/

public static void swap(int []arr,int a ,int b){

int temp=arr[a];

arr[a] = arr[b];

arr[b] = temp;

}

}

最后

底部排序是一种选择排序。整个过程主要由构建初始桩+交换桩的顶部和最后一个元素以及重建桩两部分组成。构造第一个堆的复杂度推导出为 O(n)。在交换和重建堆的过程中，必须交换n-1次。在重建堆的过程中，根据完全二叉树的性质，[log2(n -1),log2(n-2)...1]逐渐减小，大约为nlogn。因此，堆排序的时间复杂度一般认为是O(nlogn)级别。