我目前正在研究排序算法，需要实现HeapSort和Introspective Sort。
我想我已经成功实现了 HeapSort（代码有效，尝试了数百万个随机大小的随机数组，总是有效），这是我的代码：
public static <T extends Comparable<? super T>> void hsort(T[] a) {
int n = a.length;
if(n < 2) return;
/* Heapify */
for(int i = (n-2)/2; i >= 0; i--)
moveDown(a, i, n);
for(int i = n-1; i > 0; i--) {
swap(a, 0, i);
moveDown(a, 0, i);
}
}
moveDown 代码是：
private static <T extends Comparable <? super T>> void moveDown(T[] a, int i, int max) {
T e = a[i];
int j; /* Son index */
while((j = (2*i)+1) < max) {
if(j+1 < max && a[j+1].compareTo(a[j]) > 0) j++; /* Biggest son */
if(e.compareTo(a[j]) >= 0) break;
a[i] = a[j];
i = j;
}
a[i] = e;
}
这两种方法应该工作得很好，我已经测试了很多次，我从来没有遇到任何问题。
我也试图从这两种方法开始并实现内省排序，我的代码是这样的：
public static <T extends Comparable<? super T>> void introSort(T[] a) {
int size = a.length;
if(size < 2) return;
int log = Integer.SIZE - Integer.numberOfLeadingZeros(size);
introSort(a, 0, size-1, 2*log);
}
private static <T extends Comparable<? super T>> void introSort(T[] a, int min, int max, int lev) {
if(max - min < ISORT_THRESHOLD) isort(a, min, max); // Small intervall
else if(lev == 0) hsortAux(a, min, max); // HeapSort on Array Portion
else {
// QuickSort
while (min < max) {
lev--;
/* Tukey approximation */
int t = tukeyApproximation(a, min, max-1);
//t = min; Ignore this for now and read below this code
T p = a[t];
int i = min, j = max;
do {
while(a[i].compareTo(p) < 0) i++;
while(a[j].compareTo(p) > 0) j--;
if(i <= j) {
swap(a, i, j);
i++; j--;
}
} while(i <= j);
introSort(a, min, j, lev);
min = i;
}
}
}
我认为上面的代码也很好，假设方法 isort 和 hsortAux 工作正常。在我的测试中，我注意到它仅在调用 heapsort 时才会失败。当我使用 tukey 近似值来确定枢轴索引时，以及当我选择一个随机枢轴（例如总是数组的第一个元素）时，代码应该可以工作（目标是让它工作）。使用 QuickSort 的分区应该是正确的，因为我已经尝试了许多快速排序实现并且它们都可以工作，而且正如我已经说过的，当不调用 heapsort 时代码可以工作。分区实际上是另一种完美工作方法中快速排序的复制粘贴。
我确定方法 isort 和 tukeyApproximation 可以按预期工作，因为我已经单独测试了它们并在快速排序实现上进行了测试，它们工作得很好。
但是，我似乎无法实现仅在 min 和 max 之间的数组部分上完成其工作的堆排序（称为 hsortAux 的方法）。我花了几个小时在这里和谷歌上寻找答案，我试图通过查看其他人的代码来实现我自己的版本，但我多次失败，在这里我在浪费你的时间:)。一旦我设法进行了工作 heapSort 但当 tukey 近似值未选择枢轴时（例如数组的第一个元素或该部分中的随机元素），它似乎不起作用。
这是我当前的 hsortAux 代码，源自原始 hsortAux：
private static <T extends Comparable<? super T>> void hsortAux(T[] a, int min, int max) {
for(int i = (min + max - 1)/2 ; i >= min; i--)
moveDownAux(a, min, i, max+1);
for(int i = max; i > min; i--) {
swap(a, min, i);
moveDownAux(a, min, min, i);
}
}
moveDownAux 应该是仅适用于数组部分的 moveDown 方法，但是我真的不知道如何实现它，我尝试使用以前的 moveDown 方法，但它显然根本不起作用。在实现 moveDownAux 时，我什至不确定是否需要名为min的变量。
这是我当前的 moveDownAux 方法：
private static <T extends Comparable<? super T>> void moveDownAux(T[] a, int min, int i, int max) {
T e = a[i];
int j; /* Son */
while((j = (2*i)+1) < max-1) {
if(j+1 < max && a[j+1].compareTo(a[j]) > 0) j++; /* Biggest Son */
if(e.compareTo(a[j]) >= 0) break;
a[i] = a[j];
i = j;
}
a[i] = e;
}
提前感谢您的时间和答案