我正在实现我自己的QuickSort方法,但是我在返回索引时出现了第一个和最后一个出现在我的分区方法中的问题。我已经调试一行行的代码,这说明..... 排序实现 - 数组元素存在但返回-1
很显然,这些元素存在数组中,但该指数始终返回-1,这表明他们不存在阵列。
这是我的代码的样子...你能告诉为什么会发生这种情况吗?
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.Arrays;
public class Quicksort {
public static void sort(int[] arr) {
int first = arr[0];
int last = arr[arr.length - 1];
quickSort(arr, first, last);
}
private static void quickSort(int[] arr, int first, int last) {
if (first < last) {
int pivot = partition(arr, first, last);
quickSort(arr, first, pivot - 1);
quickSort(arr, pivot + 1, last);
}
}
private static int partition(int[] arr, int first, int last) {
int pivot = first;
int up = Arrays.asList(arr).indexOf(first);
int down = Arrays.asList(arr).indexOf(last);
System.out.println(up);
System.out.println(down);
do {
if (arr[up] < pivot || arr[up] != last) {
up++;
}
if (arr[down] > pivot || arr[down] != first) {
down--;
}
if (up > down) {
int temp = arr[up];
arr[up] = arr[down];
arr[down] = temp;
}
} while (up < down);
int temp = arr[down];
int pivotIndex = java.util.Arrays.asList(arr).indexOf(pivot);
arr[down] = arr[pivotIndex];
arr[pivotIndex] = temp;
return pivot;
}
public static void printArr(int[] arr) {
System.out.println(IntStream.of(arr)
.boxed()
.map(Object::toString)
.collect(Collectors.joining(", ")));
}
public static void main(String[] args) {
int[] arr = {5, 14, 30, 2, 40, 14};
printArr(arr);
sort(arr);
printArr(arr);
}
}
你在调试过程中发现了什么? –
我的调试图片在帖子中。你可以看到数组中的元素,但它返回-1 – slickset
在这一点上'up'或'down'如何有值?你的断点似乎是在这些甚至宣布之前。 –