为什么在同时对第二个数组进行排序时，这种合并排序会产生索引越界异常？
我一直在研究一种合并排序算法，我想最终用它对字符串数组进行排序。
理论上，我对一个包含ID的数组进行排序，我想按照与字符串主数组相同的顺序对其进行排序，然后对ID数组进行排序，并对字符串数组执行相同的操作，理论上对它们进行相同的排序。
例如，ID值的数组可以是[1,2,3,4,5]，而主数组看起来像["Name，1"，"Name，2"]...
当我在不包含任何第二个数组部分的情况下运行算法时，它工作正常，以下是输出：
[0,1,1,10,12,16,18,24,26,53,53,53100]
但是一旦我尝试添加第二个数组操作，我就会得到一个异常：
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1
at s4001175.ct5057.flight.Booker.merge(Booker.java:250)
at s4001175.ct5057.flight.Booker.mergeSort(Booker.java:236)
at s4001175.ct5057.flight.Booker.mergeSort(Booker.java:232)
at s4001175.ct5057.flight.Booker.mergeSort(Booker.java:232)
at s4001175.ct5057.flight.FlightManagement.passengerStatus(FlightManagement.java:92)
at s4001175.ct5057.flight.FlightManagement.mainMenu(FlightManagement.java:53)
at s4001175.ct5057.flight.FlightManagement.main(FlightManagement.java:27)
代码：
public void mergeSort(int[] flightIDArr, int arrLength, String[] actualArr) {
// Flattened array of bookings to 1d array
String[] flatArray = flattenArray(readBookings());
// If array does not need to be split as length is already 1
if (arrLength < 2) {
return;
}
// Middle of the array
int mid = arrLength / 2;
//Left array of length of half of the array
int[] left = new int[mid];
// Other half of split array, with arrLength-mid size to ensure that it works even if the array is an odd length
int[] right = new int[arrLength - mid];
//Mirrored version of previous lines but for string array of what we actually want to sort (booking info)
String[] actualLeft = new String[mid];
// Same as above but right side
String[] actualRight = new String[arrLength - mid];
// for the elements in left array
for (int i = 0; i < mid; i++) {
// filling the left arrays with the info from the full array
left[i] = flightIDArr[i];
actualLeft[i] = flatArray[i];
}
// for elements in right array
for (int i = mid; i < arrLength; i++) {
// filling the right arrays with the info from the full array
right[i - mid] = flightIDArr[i];
actualRight[i - mid] = flatArray[i];
}
//recursively calls the mergesort algorithm to split the arrays as small as possible
mergeSort(left, mid, actualLeft);
mergeSort(right, arrLength - mid, actualRight);
//re merges the split arrays
merge(flightIDArr,actualArr, left, right, mid, arrLength - mid, actualLeft,actualRight);
}
//Method to merge all the split arrays
public void merge(
int[] flightIDArr, String[] actualArr, int[] leftArr, int[] rightArr, int left, int right, String[] actualLeft, String[] actualRight) {
//setting up variables for looping
int i = 0, j = 0, k = 0;
//
while (i < left && j < right) {
if (leftArr[i] <= rightArr[j]) {
flightIDArr[k++] = leftArr[i++];
actualArr[k++] = actualLeft[i++];
}
else {
flightIDArr[k++] = rightArr[j++];
actualArr[k++] = actualRight[i++];
}
}
while (i < left) {
flightIDArr[k++] = leftArr[i++];
actualArr[k++] = actualLeft[i++];
}
while (j < right) {
flightIDArr[k++] = rightArr[j++];
actualArr[k++] = actualRight[j++];
}
// System.out.println(Arrays.toString(actualArr));
System.out.println(Arrays.toString(flightIDArr));
}
我曾尝试使用IntelliJ中的调试器运行该程序，当在第250行开始生成异常时，以下是相关变量的值：
leftArr: 0:0
actualLeft:
0:
"Booking Number: 1
Flight Number: 000
Passenger Name: Test Name
Seat Number: 1
Seat Class: First"
因此，看起来当代码达到这一阶段时，它试图将这些数组中的值设置在它们的范围之外，但在没有涉及第二个数组的情况下运行算法时不会发生这种情况，尽管在第249行似乎发生了同样的情况，其中
flightIDArr[k++] = leftArr[i++];
被称为
编辑新代码：
使用建议的答案，我修改了代码，似乎消除了错误，但排序不再正确，一些数字甚至没有包括在内：
正确的输出：
[0, 1, 1, 10, 12, 16, 18, 24, 26, 53, 53, 53, 100]
Vs新代码的当前输出：
[0, 1, 1, 1, 12, 16, 18, 18, 24, 53, 53, 53, 100]
如您所见，原始数据集中现在存在重复和缺失的值。
代码：
public void mergeSort(int[] flightIDArr, int arrLength, String[] actualArr) {
// Flattened array of bookings to 1d array
String[] flatArray = flattenArray(readBookings());
// If array does not need to be split as length is already 1
if (arrLength < 2) {
return;
}
// Middle of the array
int mid = arrLength / 2;
//Left array of length of half of the array
int[] left = new int[mid];
// Other half of split array, with arrLength-mid size to ensure that it works even if the array is an odd length
int[] right = new int[arrLength - mid];
//Mirrored version of previous lines but for string array of what we actually want to sort (booking info)
String[] actualLeft = new String[mid];
// Same as above but right side
String[] actualRight = new String[arrLength - mid];
// for the elements in left array
for (int i = 0; i < mid; i++) {
// filling the left arrays with the info from the full array
left[i] = flightIDArr[i];
actualLeft[i] = flatArray[i];
}
// for elements in right array
for (int i = mid; i < arrLength; i++) {
// filling the right arrays with the info from the full array
right[i - mid] = flightIDArr[i];
actualRight[i - mid] = flatArray[i];
}
//recursively calls the mergesort alhtml" target="_blank">gorithm to split the arrays as small as possible
mergeSort(left, mid, actualLeft);
mergeSort(right, arrLength - mid, actualRight);
//re merges the split arrays
merge(flightIDArr,actualArr, left, right, mid, arrLength - mid, actualLeft,actualRight);
}
//Method to merge all the split arrays
public void merge(
int[] flightIDArr, String[] actualArr, int[] leftArr, int[] rightArr, int left, int right, String[] actualLeft, String[] actualRight) {
//setting up variables for looping
int i = 0, j = 0, k = 0;
//
while (i < left && j < right) {
if (leftArr[i] <= rightArr[j]) {
flightIDArr[k] = leftArr[i];
actualArr[k++] = actualLeft[i++];
}
else {
flightIDArr[k] = rightArr[j];
actualArr[k++] = actualRight[i++];
}
}
while (i < left) {
flightIDArr[k] = leftArr[i];
actualArr[k++] = actualLeft[i++];
}
while (j < right) {
flightIDArr[k] = rightArr[j];
actualArr[k++] = actualRight[j++];
}
// System.out.println(Arrays.toString(ActualArr));
System.out.println(Arrays.toString(flightIDArr));
// System.out.println(" Actual Array: \n \n " +(Arrays.toString (actualArr)));
}
共有1个答案
使用kj等时，会增加变量。对左数组和右数组都执行此操作。但你可能只想做一次，而不是两次。
您想像这样替换代码：
if (leftArr[i] <= rightArr[j]) {
flightIDArr[k++] = leftArr[i++];
actualArr[k++] = actualLeft[i++];
}
有了这个：
if (leftArr[i] <= rightArr[j]) {
flightIDArr[k] = leftArr[i];
actualArr[k++] = actualLeft[i++];
}
或者这个：
if (leftArr[i] <= rightArr[j]) {
flightIDArr[k] = leftArr[i];
actualArr[k] = actualLeft[i];
k++; i++;
}
-
我正在为我的算法类做一个赋值，我必须证明内部合并排序的时间复杂度为O（n logn）。为此，我制作了长度从10000个元素到75000个元素的数组。然后，我将随机数加载到10000以下的数组中，并将数组长度与排序所需的时间一起输出到控制台。 奇怪的结果是，有些数组需要约15毫秒的给定或获取，而另一些数组则需要0毫秒，即使数组的长度要长数万个整数。你知道为什么吗？我可以上传输出的屏幕截图，但需要有人
-
介绍 考虑以下示例： 使用运行以升序打印数组中的排序数字： 问题 考虑两个(一般来说，对于< code>N)对应数组< code>a和< code>b的扩展情况 以及“同时”排序所有数组的问题..为了实现这一点，我需要对数组< code>a进行排序，还需要获取排序的索引。对于这个简单的例子，指数由下式给出 有了这些索引，我就可以根据数组 的排序结果打印出排序后的 数组。例如： 将打印排序的数组。。
-
我正在学习对整数数组进行合并排序，当我注意到将排序后的数组元素复制到原始数组时，我们需要同时运行两个单独的循环变量，而这些索引处的值被复制到原始数组。以下是参考代码： 请注意，在将数组的值复制到数组时，我们使用了两个单独的变量和。我确实尝试只使用一个循环变量，如下所示： 但收到了不正确的输出。如果有人知道为什么我们需要两个独立的变量来进行操作，请告诉我。谢谢：）
-
我想用Javascript实现合并排序作为一种学习经验。我有mergeSort（unsortedArray）函数，它接受一个未经排序的数组，并使用合并排序策略对其进行排序。mergeSort（）调用merge（leftArray,rightArray）,后者将两个数组合并在一起,得到一个数组。 我认为问题出在merge（）函数上。在数组[8,8,7,5,4,6,3,2,1,5,9,8,7,6,5,
-
对于这个项目，我得到了一个字符串数组和一个整数数组。int[1]是字符串[1]的排名。我需要使用mergesort按1到n的顺序对int数组进行排序，我在下面已经完成了这项工作。但是当int数组被移动时，我还需要切换字符串数组的位置，以便它们都被排序，如果这有意义的话？我不知道我的编码有什么问题，甚至我的想法是否真的有效，但我一直在stringSorted[k]=stringRight[j]上得到
-
我正在学习Python和一些基本的数据结构和算法。我实现了自己版本的合并排序，但我不明白为什么它会改变输入数组的顺序。它的行为就像我在mergesort（）函数中将输入数组作为全局引用一样，但我没有这样做。从我实现代码的方式来看，我认为应该在函数的本地范围内对输入数组的副本进行排序，然后返回该副本的排序版本，保持输入数组不变。然而，事实并非如此。它正确地对数组排序；我只是被一个似乎是范围问题的问题