package heapSort;
import org.junit.Test;
public class Main {
/**
* 堆调整算法
*
* @param num 数组
* @param s 调整节序号
* @param l 数组排序最大的序号
*/
public void HeapAdjust(int[] num, int s, int l) {
int i, j;
int temp = num[s];
i = s;
// 根据二叉树的性质可知道每一个序号对应的子节点以及双亲节点
for (j = 2 * i + 1; j <= l; j = 2 * j + 1) {
//判断如果j指向数值较大的节点
if (j < l && num[j] < num[j + 1]) {
j = j + 1;
}
//如果调整节点大于其子节点最大的值则无需调整
if (temp > num[j]) {
break;
}
//如果小于则将子节点移动到根节点位置，如果还存在子节点则继续判断调整位置的子节点
//准备继续向下 调整节点
num[i] = num[j];
i = j;
}
//最后插入数据
num[i] = temp;
}
/**
* 堆建立初始化函数
*
* @param nums 数组序列
* @param l 最大序号
*/
public void HeapInit(int[] nums, int l) {
for (int i = (l - 1) / 2; i >= 0; i--) {
HeapAdjust(nums, i, l);
}
}
public void HeapSort(int[] nums, int l) {
for (int i = l; i > 0; i--) {
int temp = nums[0];
nums[0] = nums[i];
nums[i] = temp;
//因为每次调整都是对根节点进行调整所以下列方法s永远为0
HeapAdjust(nums, 0, i - 1);
}
}
@Test
public void test() {
int[] nums = {3, 2, 4, 9, 8,1,7};
int l=nums.length-1;
HeapInit(nums, l);
HeapSort(nums, l);
for (int n : nums)
System.out.println(n);
}
堆排序
?著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 选择排序 对于任何输入，时间为O(n*n)； 冒泡排序 最优（对于升序的数组，因为加入了一个跳出判断）：O(n)，...
- [前言] 此文章参考自《数据结构（java版）》第三版，叶核亚 一、排序的基本概念： （1）性能评价：取决于时间复...
