【游戏开发】排序算法之堆排序
父子节点的对应索引关系推导
假定我们拿到这样一个数组, 并且把它表示成以下的树结构
设:
P 是父节点对应数组的索引
C 是左子节点对应数组的索引
i 是子节点所在二叉树的层次
j 是子节点所在层次的偏移量
拿上图举例, P == 1(父节点 6), C == 3(子节点 5), i == 1, j == 1
可以推导:
C = 2 ^ i j P = 2 ^ (i - 1) (j - 1) / 2 P = ((2 ^ i j) - 1) / 2 = (C - 1) / 2
private int getParentIndex(int child) {
return (child - 1) / 2;
}
private int getLeftChildIndex(int parent) {
return 2 * parent 1;
}
如何构建一个最大堆
假设二叉树最后一层最后一个chaild是C
小于
大于等于
int last = arr.length - 1;
// 初始化最大堆, 找到C的parent, C的基础上减一递归找平衡
for (int i = getParentIndex(last); i >= 0; --i) {
adjustHeap(i, last);
}
private void adjustHeap(int i, int len) {
int left,
right,
j;
// 获取父节点i的左子
left = getLeftChildIndex(i);
// 如果i有子节点
while (left <= len) {
// i的右子
right = left 1;
j = left;
// 找出左右子最大的值
if (j < len && arr[left] < arr[right]) {
j ;
}
// 父节点小于子节点最大值
if (arr[i] < arr[j]) {
// 父子替换
swap(array, i, j);
// 替换后的父节点向下寻找看有没有比它大的子节点
i = j;
left = getLeftChildIndex(i);
} else {
break; // 停止筛选
}
}
}
算法思路
借助 数据结构-堆
的思想, 假定数组长度 n, 定义 i = n
最大堆
public static void sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int length = arr.length;
for (int i = getParentIndex(length - 1); i >= 0; i--) {
ajustHeap(arr, i, length - 1);
}
int i = length - 1;
while (i > 0) {
swap(arr, 0, i);
i--;
ajustHeap(arr, 0, i);
}
}
时间复杂度
O(nlogn)
初始化建堆过程时间:O(n) 更改堆元素后重建堆时间:O(nlogn) f(n) = n nlogn = n(logn 1) = O(nlogn)
推算过程:
首先要理解怎么计算这个堆化过程所消耗的时间,可以直接画图去理解;
假设高度为k,则从倒数第二层右边的节点开始,这一层的节点都要执行子节点比较然后交换(如果顺序是对的就不用交换);倒数第三层呢,则会选择其子节点进行比较和交换,如果没交换就可以不用再执行下去了。如果交换了,那么又要选择一支子树进行比较和交换;
那么总的时间计算为:s = 2^( i - 1 ) * ( k - i );其中 i 表示第几层,2^( i - 1) 表示该层上有多少个元素,( k - i) 表示子树上要比较的次数,如果在最差的条件下,就是比较次数后还要交换;因为这个是常数,所以提出来后可以忽略;
S = 2^(k-2) * 1 2^(k-3) 2….. 2 (k-2) 2^(0)*(k-1) ===> 因为叶子层不用交换,所以i从 k-1 开始到 1;
这个等式求解,我想高中已经会了:等式左右乘上2,然后和原来的等式相减,就变成了:
S = 2^(k - 1) 2^(k - 2) 2^(k - 3) ….. 2 - (k-1)
除最后一项外,就是一个等比数列了,直接用求和公式:S = { a1[ 1- (q^n) ] } / (1-q);
S = 2^k -k -1;又因为k为完全二叉树的深度,所以 (2^k) <= n < (2^k -1 ),总之可以认为:k = logn (实际计算得到应该是 log(n 1) < k <= logn );
综上所述得到:S = n - longn -1,所以时间复杂度为:O(n)
更改堆元素后重建堆时间:O(nlogn)
推算过程:
1、循环 n -1 次,每次都是从根节点往下循环查找,所以每一次时间是 logn,总时间:logn(n-1) = nlogn - logn ;
完整代码:
class HeapSort {
public static void sort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int length = arr.length;
for (int i = getParentIndex(length - 1); i >= 0; i--) {
ajustHeap(arr, i, length - 1);
}
int i = length - 1;
while (i > 0) {
swap(arr, 0, i);
i--;
ajustHeap(arr, 0, i);
}
}
private static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
private static void ajustHeap(int[] arr, int start, int end) {
int left = getLeftChildIndex(start);
while (left <= end) {
int right = left 1;
int target = left;
if (right <= end && arr[left] < arr[right]) {
target = right;
}
if (arr[start] < arr[target]) {
swap(arr, start, target);
start = target;
left = getLeftChildIndex(start);
} else {
break;
}
}
}
private static int getParentIndex(int child) {
return (child - 1) / 2;
}
private static int getLeftChildIndex(int parent) {
return 2 * parent 1;
}
public static void main(String[] args) {
int[] array = {
111,
52,
77,
98,
36,
12,
13,
48,
79,
10,
6,
500
};
sort(array);
System.out.println(arrayToString(array));
}
private static String arrayToString(int[] array) {
StringBuilder builder = new StringBuilder();
for (int t: array) {
builder.append(t " ");
}
return builder.toString();
}
}
转载声明:本文来源于网络,不作任何商业用途。

全部评论


暂无留言,赶紧抢占沙发
热门资讯

专访|王氏教育集团康海威老师:国民手游《王者荣耀》曹操高低模打造者...

当代”毕加索“插画家John Battalgazi几何图形作品...

韩国画师“pilyeon”的这组线稿,都把我看哭了!...

适合30岁女人的职业有哪些?

超人气治愈系艺术家吉田誠治场景参考

严禁刷票警告!!!

第19届王座杯CG大赛:获奖作品公布!

完美世界游戏全新品牌升级

综艺节目《向往的生活》花子设计的秘密
