这是我的介绍代码。我无法使代码的堆排序部分正常工作。
partition() 和 sort() 工作正常，但堆排序部分排序不正确。我得到这样的排序数组 (size=10):
10
18
26
35
25
39
49
49
57
89
除了少数数字外，大部分都是排序的。我只是尝试在每个 heapsort() 调用中对数组的一部分进行排序。
public class IntroSort {
public static void sort(int[] arrayToSort){
int depth = ((int) Math.log(arrayToSort.length))*2;
sort(arrayToSort, depth, 0, arrayToSort.length-1);
}
private static void sort(int[] arrayToSort, int depth, int start, int end){
int length = arrayToSort.length;
if(length <= 1){
return;
}else if(depth == 0){
heapSort(arrayToSort, start, end);
}else{
if(start >= end)
return;
int pivot = arrayToSort[(start + end)/2];
int index = partition(arrayToSort, start, end, pivot);
sort(arrayToSort, depth-1, start, index-1);
sort(arrayToSort, depth-1, index, end);
}
}
private static void heapSort(int[] arrayToSort, int start, int end){
for (int i = end / 2 - 1; i >= start; i--)
heapify(arrayToSort, end, i);
for (int i=end-1; i>=start; i--){
int temp = arrayToSort[start];
arrayToSort[start] = arrayToSort[i];
arrayToSort[i] = temp;
heapify(arrayToSort, i, start);
}
}
private static void heapify(int[] arrayToSort, int n, int i){
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arrayToSort[l] > arrayToSort[largest])
largest = l;
if (r < n && arrayToSort[r] > arrayToSort[largest])
largest = r;
if (largest != i){
int swap = arrayToSort[i];
arrayToSort[i] = arrayToSort[largest];
arrayToSort[largest] = swap;
heapify(arrayToSort, n, largest);
}
}
private static int partition(int[] arrayToSort, int start, int end, int pivot){
while(start <= end){
while(arrayToSort[start] < pivot){
start++;
}
while(arrayToSort[end] > pivot){
end--;
}
if(start <= end){
int temp = arrayToSort[start];
arrayToSort[start] = arrayToSort[end];
arrayToSort[end] = temp;
start++;
end--;
}
}
return start;
}
}
有什么想法吗？
最佳答案
卡尔顿， 我在一些数组上运行了您的代码，并且该数组中的数据已经排序。 您能否举例说明您的算法无法正常工作。
int[] arr = new int[]{17,1,15,1,2,3,18,100,100,454};
heapSort(arr, 0, arr.length);
for (int i:arr)
System.out.print(i+" ");
结果我得到了:
1 1 2 3 15 17 18 100 100 454
进程结束，退出代码为 0
关于java - 使用堆排序对数组的一部分进行排序，bug，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43016874/