我正在尝试一些堆在java中的乐趣。在java代码中进行堆排序?
首先,我创建一个最大堆。然后将第一个元素设置为变量max,将最后一个项目从未安排的数组移动到堆顶部,然后按下。
我试过21个元素,它可以正常工作70%,我想知道是否有人发现问题。
谢谢。
public class HeapSort extends Sort{
public int sort(int arr[]) {
for (int i = 1; i < arr.length; i++) {
// add to heap
int p = i;
int pp = p /2 ;
while (p > 0 && arr[pp] < arr[p]) {
swap(arr, p, pp);
p = pp;
pp = p/2;
}
}
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
int p = 0;
int child1 = (p << 1) + 1;
int child2 = (p << 1) + 2;
while (child2 < i || child1 < i) {
if (child1 >= i) {
if (arr[p] < arr[child2]) {
swap(arr, p, child2);
p = child2;
} else {
break;
}
} else if (child2 >= i) {
if (arr[p] < arr[child1]) {
swap(arr, p, child1);
p = child1;
} else {
break;
}
} else {
int minIdx = arr[child1] < arr[child2] ? child1 : child2;
int maxIdx = child1 == minIdx ? child2 : child1;
if (arr[p] < arr[maxIdx]) {
swap(arr, p, maxIdx);
p = maxIdx;
} else {
break;
}
}
child1 = (p << 1) + 1;
child2 = (p << 1) + 2;
}
}
return 0;
}
void swap(int arr[], int idx1, int idx2) {
int tmp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = tmp;
}
public String toString() {
return "HeapSort";
}
}
我觉得http://codereview.stackexchange.com/更适合这样的问题。 –