java - Java快速排序程序不排序数组,arrayoutofbounds异常
问题描述
我正在学习快速排序算法。我不确定我哪里出错了。我相信我已经正确地实现了这个算法,因为它对一些随机值进行了排序,但其他一些则没有。尝试调试此问题时,我已将数组的大小更改为 3 而不是最初的 20。这是我当前的实现:
public class Quicksort {
public static void main(String[] args) {
// Generate a random array of integers to sort
// Integer[] numbers = new Integer[20];
// testing int, above is original
Integer[] numbers = new Integer[3];
for (int i = 0; i < numbers.length; i++) {
numbers[i] = (int) (Math.random() * 100);
}
// Print unsorted array
printArray(numbers);
// Sort array
quicksort(numbers);
// Print sorted array
printArray(numbers);
}
// Print a comma-separated list of the elements in array
public static <T> void printArray(T[] array) {
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + (i < array.length - 1 ? ", " : "\n"));
}
}
// Print a comma-separated list of the elements in array drawing attention to
// the pivot and bounds of the partition
public static <T> void printArrayPartition(T[] array, int low, int high, int pivot) {
for (int i = 0; i < array.length; i++) {
String element = "" + array[i];
if (i == pivot)
element = "*" + element + "*";
if (i == low)
element = "[" + element;
if (i == high)
element += "]";
System.out.print(element + (i < array.length - 1 ? ", " : "\n"));
}
}
// This is a shortcut to call the recursive quicksort on the entire array
public static <T extends Comparable<T>> void quicksort(T[] array) {
quicksort(array, 0, array.length - 1);
}
// Recursively quicksort a partition of the array
private static <T extends Comparable<T>> void quicksort(T[] array, int low, int high) {
// If high is greater than low, then there are at least two elements in this
// partition and it needs to be sorted. Otherwise it contains at most 1 element
// and is therefore already sorted.
if (low < high) {
int pivotIndex = partition(array, low, high);
// Uncomment printArrayPartition to print the array after every partition
// (helpful for debugging). Every element within the partition (enclosed by [])
// should appear on the correct side of the pivot value (marked by **)
printArrayPartition(array, low, high, pivotIndex);
// Quicksort the left and right partitions
quicksort(array, low, pivotIndex - 1);
quicksort(array, pivotIndex + 1, high);
}
}
// Split a partition of the array into two new partitions and one pivot. The
// left partition includes everything less than the pivot, and the right
// partition is everything greater than or equal to the pivot (excluding the
// pivot, which remains between the two partitions). Returns the index of the
// pivot.
private static <T extends Comparable<T>> int partition(T[] array, int low, int high) {
// Use the last element of the partition as the pivot
T pivotValue = array[high];
//int pivot = (int) pivotValue;
// This marks the index AFTER the end of the (new) left partition. Right now
// there is no left partition, so it's at the beginning of the partition we're
// currently splitting up.
int left = low;
// For each element in the partition (except the pivot)
for (int i = 0; i < array.length; i++) {
// Compare the current element to the pivot (high)
if (array[i].compareTo(pivotValue) < 0) {
// If the current element is less than the pivot, swap it with the leftmost
// unpartitioned element (making it part of the left partition) and update the
// left partition
swap(array, left, i);
left++;
}
}
// Swap the pivot with the leftmost unpartitioned element. The unpartitioned
// elements are now the right partition.
swap(array, high, left);
// Return the new index of the pivot
return left;
}
// Swap the elements of array at index a and index b
private static <T> void swap(T[] array, int a, int b) {
T temp = array[a];
array[a] = array[b];
array[b] = temp;
}
}
我收到的编译错误消息:
58, 89, 53
[*53*, 89, 58]
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
at Quicksort.swap(Quicksort.java:103)
at Quicksort.partition(Quicksort.java:89)
at Quicksort.quicksort(Quicksort.java:54)
at Quicksort.quicksort(Quicksort.java:62)
at Quicksort.quicksort(Quicksort.java:45)
at Quicksort.main(Quicksort.java:15)
我看不到这个问题。任何帮助是极大的赞赏。
解决方案
你的界限partition()
不正确。而不是像您一样遍历整个数组
for (int i = 0; i < array.length; i++)
您应该迭代您实际分区的部分:
for (int i = low; i < high; i++)
推荐阅读
- c++ - 打开文件进行读取时应用程序随机挂起
- git - git commit w/o message 后被困在 vim 调试窗口中
- python - 无法使用 yapf 设置/使用旋钮(谷歌的 Python 格式化程序)
- apache-camel - Weblogic 12.2 中的 Apache Camel LRUCacheFactory 死锁
- r - 如何重新排列行?
- reactjs - 使用多个 setHook 会使组件多次渲染?
- python-3.x - 始终处理但并不总是产生的生成器函数
- excel - 如果您连续更改单元格值,请添加标识符
- config - 强制重新加载 clickhouse 配置?
- xamarin.android - Xamarin.Android 在 MVVMCross 加载器中滑动以刷新无限加载