java - CountSort 数组超出索引

Question

我正在为我的大学类(class)实现 CountSort。我编写了一个工作代码，对于较小尺寸的数组(25 个值)来说效果很好，但是当我尝试使用多个数组大小运行这个代码时，会抛出 arrayoutofbounds 异常，我不太清楚为什么。在我看来，数组大小不应该有任何问题，但是任何有关正在发生的事情以及如何修复它的输入将不胜感激! :)

import java.util.*;

public class CountSortMore
{
public static void main(String[] args)
{
    int SIZE = 0;
    int sizeList[] = {1000, 10000, 100000, 500000, 1000000};
    int[] nums = null;
    for (int sizeI = 0; sizeI < sizeList.length; sizeI++)
    {
        SIZE = sizeList[sizeI];
        nums = new int[SIZE];

        //random num generation up to 100000
        for (int i = 0; i < SIZE; i++)
        nums[i] = (int)(Math.random()*100000);

        //for (int i = 0; i < SIZE; i++)
        //{ 
        //  System.out.print(nums[i]);
        //  System.out.println("");
        //}

        //call CountSort
        final long startTime = System.currentTimeMillis();
            countSort(nums, 0, SIZE -1);
        final long endTime = System.currentTimeMillis();
            System.out.println("For n = " + SIZE + ", execution time = " + (endTime - startTime) );

        //verify sorting
        //for (int i = 0; i < SIZE; i++)
        //{
        //  System.out.print(nums[i]);
        //  System.out.println("");
        //}
    }
}

public static void countSort(int[] nums, int low, int high)
{
    int[] counts = new int[high - low +1];
    for (int x : nums)
        counts[x - low]++;
    int current = 0;
    for (int i = 0; i < counts.length; i++)
    {
        Arrays.fill(nums, current, current + counts[i], i + low);
        current += counts[i];
    }
}
}

Answer 1

我在这里看到一个问题:

for (int x : nums)
    counts[x - low]++;

您正在使用 0-99999 范围内的随机数对 count[] 数组进行索引，但最小的数组只有 1000 长。

虽然我认为你的方法从根本上来说是有缺陷的，但你可以通过将随机范围限制为SIZE来避免爆炸(我没有仔细查看你的代码来弄清楚它的意图是什么)。

<小时/>

此外，请考虑使用 foreach 循环。而不是:

int SIZE;
for (int sizeI = 0; sizeI < sizeList.length; sizeI++) {
    SIZE = sizeList[sizeI];

仅使用:

for (int SIZE : sizeList) {

您可能想回顾一下有关 Java 命名标准的章节。