算法ITeye - 娱乐之横扫全球

算法ITeye

2019-01-11 19:14:30 | 作者: 谷冬 | 标签: 节点,算法,一个 | 浏览: 2685

堆排序(Heapsort)是指使用堆这种数据结构所规划的一种排序算法。堆积是一个近似彻底二叉树的结构,并一起满意堆积的性质:即子结点的键值或索引总是小于(或许大于)它的父节点。

堆排序的均匀时刻复杂度为Ο(nlogn) 。

算法过程:

创立一个堆H[0..n-1]

把堆首(最大值)和堆尾交流

3. 把堆的尺度缩小1,并调用shift_down(0),意图是把新的数组顶端数据调整到相应方位

4. 重复过程2,直到堆的尺度为1



 

 

public class HeapSort {
 public static void main(String[] args) {
 int[] a = { 50, 38, 65, 97, 76, 1, 27, 49, 78};
 int arrayLength = a.length;
 // 循环建堆
 for (int i = 0; i arrayLength - 1; i++) {
 // 建堆
 buildHeap(a, arrayLength - 1 - i);
 // 交流堆顶和最终一个元素
 swap(a, 0, arrayLength - 1 - i);
 System.out.println(Arrays.toString(a));
 // 对data数组从0到lastIndex建大顶堆
 public static void buildHeap(int[] data, int lastIndex) {
 // 从lastIndex处节点(最终一个节点)的父节点开端
 for (int i = (lastIndex - 1) / 2; i i--) {
 // k保存正在判别的节点
 int k = i;
 // 假如当时k节点的子节点存在
 while (k * 2 + 1 = lastIndex) {
 // k节点的左子节点的索引
 int biggerIndex = 2 * k + 1;
 // 假如biggerIndex小于lastIndex,即biggerIndex+1代表的k节点的右子节点存在
 if (biggerIndex lastIndex) {
 // 若果右子节点的值较大
 if (data[biggerIndex] data[biggerIndex + 1]) {
 // biggerIndex总是记载较大子节点的索引
 biggerIndex++;
 // 假如k节点的值小于其较大的子节点的值
 if (data[k] data[biggerIndex]) {
 // 交流他们
 swap(data, k, biggerIndex);
 // 将biggerIndex赋予k,开端while循环的下一次循环,从头确保k节点的值大于其左右子节点的值
 k = biggerIndex;
 } else {
 break;
 // 交流
 private static void swap(int[] data, int i, int j) {
 int tmp = data[i];
 data[i] = data[j];
 data[j] = tmp;
}

 

 

版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表娱乐之横扫全球立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章